Интервью Google: организация блоков

Ответ 1

Это проблема подсчета, а не проблема построения, поэтому мы можем обратиться к ней с помощью рекурсии. Так как проблема имеет две естественные части, глядя слева и глядя справа, разбейте ее и разрешите только для одной части.

Пусть b(N, L, R) - число решений, а f(N, L) - количество аранжировок блоков N, так что L видны слева. Сначала подумайте о f, потому что это проще.

ПОДХОД 1

Пусть получают начальные условия, а затем идут для рекурсии. Если все должно быть видимым, то их нужно заказывать все чаще, поэтому

f(N, N) = 1

Если предполагается, что это более видимые блоки, чем доступные блоки, то мы ничего не можем сделать, поэтому

f(N, M) = 0 if N < M

Если только один блок должен быть видимым, тогда сначала ставьте наибольшее, а затем остальные могут следовать в любом порядке, поэтому

f(N,1) = (N-1)!

Наконец, для рекурсии подумайте о позиции самого высокого блока, скажем, N находится в k th месте слева. Затем выберите блоки, которые должны быть расположены перед ним в (N-1 choose k-1) способами, упорядочите эти блоки так, чтобы точно L-1 были видны слева, и закажите N-k блоки за N в любом из них, указав:

f(N, L) = sum_{1<=k<=N} (N-1 choose k-1) * f(k-1, L-1) * (N-k)! 

Фактически, поскольку f(x-1,L-1) = 0 для x<L, мы можем также начать k в L вместо 1:

f(N, L) = sum_{L<=k<=N} (N-1 choose k-1) * f(k-1, L-1) * (N-k)! 

Правильно, поэтому теперь, когда будет понят более простой бит, используйте f для решения более сложного бита b. Опять же, используйте рекурсию на основе положения самого высокого блока, снова скажем, что N находится в позиции k слева. Как и прежде, выберите блоки перед ним в N-1 choose k-1 способами, но теперь подумайте о каждой стороне этого блока отдельно. Для блоков k-1, оставшихся от N, убедитесь, что они точно видны с помощью L-1. Для блока N-k справа от N убедитесь, что R-1 видны, а затем отмените порядок, который вы получите от f. Поэтому ответ:

b(N,L,R) = sum_{1<=k<=N}  (N-1 choose k-1) * f(k-1, L-1) * f(N-k, R-1)

где f полностью выработано выше. Опять же, многие члены будут равны нулю, поэтому мы хотим только взять k, чтобы k-1 >= L-1 и N-k >= R-1 получить

b(N,L,R) = sum_{L <= k <= N-R+1}  (N-1 choose k-1) * f(k-1, L-1) * f(N-k, R-1)

ПОДХОД 2

Я снова подумал об этой проблеме и нашел несколько более хороший подход, который позволяет избежать суммирования.

Если вы работаете с проблемой противоположным образом, думайте о добавлении наименьшего блока вместо самого большого блока, то повторение для f становится намного проще. В этом случае с теми же начальными условиями рекуррентность

f(N,L) = f(N-1,L-1) + (N-1) * f(N-1,L)

где первое слагаемое f(N-1,L-1) происходит от размещения самого маленького блока в крайнем левом положении, тем самым добавляя еще один видимый блок (следовательно, L уменьшается до L-1), а второе слагаемое (N-1) * f(N-1,L) счета для размещения самого маленького блока в любой из N-1 непередовых позиций, и в этом случае он не отображается (следовательно, L остается фиксированным).

Эта рекурсия имеет то преимущество, что всегда уменьшается N, хотя это затрудняет просмотр некоторых формул, например f(N,N-1) = (N choose 2). Эта формула довольно легко показать из предыдущей формулы, хотя я не уверен, как извлечь ее из этого более простого повторения.

Теперь, чтобы вернуться к исходной проблеме и решить ее для b, мы также можем использовать другой подход. Вместо того, чтобы суммировать раньше, подумайте о видимых блоках как входящих в пакеты, так что, если блок отображается слева, то его пакет состоит из всех блоков справа от него и перед следующим блоком, видимым слева, и аналогично, если блок отображается справа, то его пакет содержит все блоки слева от него, пока следующий блок не будет справа. Сделайте это для всех, кроме самого высокого блока. Это делает пакеты L+R. Учитывая пакеты, вы можете перемещать их с левой стороны в правую сторону, просто изменяя порядок блоков. Поэтому общий случай b(N,L,R) фактически сводится к решению случая b(N,L,1) = f(N,L), а затем выбираем, какой из пакетов поставить слева и который справа. Поэтому имеем

b(N,L,R) = (L+R choose L) * f(N,L+R)

Опять же, эта переформулировка имеет некоторые преимущества перед предыдущей версией. Объединяя эти последние две формулы, гораздо легче увидеть сложность общей проблемы. Тем не менее, я по-прежнему предпочитаю первый подход к построению решений, хотя, возможно, другие не согласятся. В целом, это просто показывает, что есть более чем один хороший способ подойти к проблеме.

Что с номерами Стирлинга?

Как указывает Джейсон, цифры f(N,L) - это точно (без знака) числа Стирлинга первого рода, Это можно увидеть сразу же из рекурсивных формул для каждого. Тем не менее, всегда приятно видеть это напрямую, поэтому здесь идет.

(без знака) числа Стирлинга первого рода, обозначенные S(N,L), подсчитывают количество перестановок N в циклы L. Учитывая перестановку, записанную в обозначении цикла, мы пишем перестановку в канонической форме, начиная цикл с наибольшим числом в этом цикле и затем упорядочивая циклы все чаще на первое число цикла. Например, перестановка

(2 6) (5 1 4) (3 7)

было бы записано в канонической форме как

(5 1 4) (6 2) (7 3)

Теперь отпустите круглые скобки и обратите внимание, что если это высота блоков, то количество видимых блоков слева - это точно количество циклов! Это связано с тем, что первое число каждого цикла блокирует все остальные числа в цикле, и первое число каждого последующего цикла видно за предыдущим циклом. Следовательно, эта проблема на самом деле просто проницательный способ попросить вас найти формулу для чисел Стирлинга.

Ответ 2

хорошо, так же как эмпирическое решение для малых N:

blocks.py:

import itertools
from collections import defaultdict

def countPermutation(p):
    n = 0
    max = 0
    for block in p:
        if block > max:
            n += 1
            max = block
    return n

def countBlocks(n):
    count = defaultdict(int)
    for p in itertools.permutations(range(1,n+1)):
        fwd = countPermutation(p)
        rev = countPermutation(reversed(p))
        count[(fwd,rev)] += 1
    return count

def printCount(count, n, places):
    for i in range(1,n+1):
        for j in range(1,n+1):
            c = count[(i,j)]
            if c > 0:
                print "%*d" % (places, count[(i,j)]),
            else:
                print " " * places ,
        print

def countAndPrint(nmax, places):
    for n in range(1,nmax+1):
        printCount(countBlocks(n), n, places)
        print

и выборки:

blocks.countAndPrint(10)
     1

            1
     1

            1      1
     1      2
     1

            2      3      1
     2      6      3
     3      3
     1

            6     11      6      1
     6     22     18      4
    11     18      6
     6      4
     1

           24     50     35     10      1
    24    100    105     40      5
    50    105     60     10
    35     40     10
    10      5
     1

          120    274    225     85     15      1
   120    548    675    340     75      6
   274    675    510    150     15
   225    340    150     20
    85     75     15
    15      6
     1

          720   1764   1624    735    175     21      1
   720   3528   4872   2940    875    126      7
  1764   4872   4410   1750    315     21
  1624   2940   1750    420     35
   735    875    315     35
   175    126     21
    21      7
     1

         5040  13068  13132   6769   1960    322     28      1
  5040  26136  39396  27076   9800   1932    196      8
 13068  39396  40614  19600   4830    588     28
 13132  27076  19600   6440    980     56
  6769   9800   4830    980     70
  1960   1932    588     56
   322    196     28
    28      8
     1

        40320 109584 118124  67284  22449   4536    546     36      1
 40320 219168 354372 269136 112245  27216   3822    288      9
109584 354372 403704 224490  68040  11466   1008     36
118124 269136 224490  90720  19110   2016     84
 67284 112245  68040  19110   2520    126
 22449  27216  11466   2016    126
  4536   3822   1008     84
   546    288     36
    36      9
     1

Вы заметите несколько очевидных (ну, в основном очевидных) вещей из заявления о проблеме:

• общее количество подстановок всегда равно N!
• за исключением N = 1, нет решения для L, R = (1,1): если счетчик в одном направлении равен 1, то он подразумевает, что самый высокий блок находится на этом конце стека, поэтому счетчик в другом направлении должен быть >= 2
• ситуация симметрична (переверните каждую перестановку, и вы отмените подсчет L, R)
• если p является перестановкой блоков N-1 и имеет счет (Lp, Rp), то N перестановок блока N, вставленных в каждое возможное пятно, может иметь счет от L = 1 до Lp + 1, и R = 1 до Rp + 1.

Из эмпирического вывода:

• крайний левый столбец или верхняя строка (где L = 1 или R = 1) с N блоками - это сумма строки/столбцы с блоками N-1: т.е. в обозначениях @PengOne,

  b(N,1,R) = sum(b(N-1,k,R-1) for k = 1 to N-R+1

• Каждая диагональ представляет собой строку треугольника Паскаля, умножая постоянный множитель K на эту диагональ - я не могу это доказать, но я уверен, что кто-то может - i.e.:

  b(N,L,R) = K * (L+R-2 choose L-1) где K = b(N,1,L+R-1)

Таким образом, вычислительная сложность вычисления b (N, L, R) такая же, как вычислительная сложность вычисления b (N, 1, L + R-1), которая является первым столбцом (или строкой) в каждом треугольнике.

Это наблюдение, вероятно, составляет 95% пути к явному решению (другие 5%, я уверен, связаны с стандартными комбинаторными тождествами, я не слишком хорошо знаком с ними). ​​

Быстрая проверка с помощью Online Encyclopedia of Integer Sequences показывает, что b (N, 1, R) представляется Последовательность OEIS A094638:

A094638 Треугольник, читаемый строками: T (n, k) = | s (n, n + 1-k) |, где s (n, k) - это подписанные числа Стирлинга первого рода (1 <= k <; = n, другими словами, беззнаковые числа Стирлинга первого рода в обратном порядке).   1, 1, 1, 1, 3, 2, 1, 6, 11, 6, 1, 10, 35, 50, 24, 1, 15, 85, 225, 274, 120, 1, 21, 175, 1624, 1764, 720, 1, 28, 322, 1960, 6769, 13132, 13068, 5040, 1, 36, 546, 4536, 22449, 67284, 118124, 109584, 40320, 1, 45, 870, 9450, 63273, 269325, 723680, 1172700

Насколько эффективно вычислить номера Стирлинга первого рода, я не уверен; Википедия дает явную формулу, но она выглядит как неприятная сумма. Этот вопрос (вычисление Stirling #s первого рода) отображается в MathOverflow, и он выглядит как O (n ^ 2), как полагает PengOne.

Ответ 3

Основываясь на ответе @PengOne, вот моя реализация Javascript:

function g(N, L, R) {
    var acc = 0;
    for (var k=1; k<=N; k++) {
        acc += comb(N-1, k-1) * f(k-1, L-1) * f(N-k, R-1);
    }
    return acc;
}

function f(N, L) {
    if (N==L) return 1;
    else if (N<L) return 0;
    else {
        var acc = 0;
        for (var k=1; k<=N; k++) {
            acc += comb(N-1, k-1) * f(k-1, L-1) * fact(N-k);
        }
        return acc;
    }
}

function comb(n, k) {
    return fact(n) / (fact(k) * fact(n-k));
}

function fact(n) {
    var acc = 1;
    for (var i=2; i<=n; i++) {
        acc *= i;
    }
    return acc;
}

$("#go").click(function () {
    alert(g($("#N").val(), $("#L").val(), $("#R").val()));
});

Ответ 4

Вот мое конструктивное решение, вдохновленное идеями @PengOne.

import itertools

def f(blocks, m):
    n = len(blocks)
    if m > n:
        return []
    if m < 0:
        return []
    if n == m:
        return [sorted(blocks)]
    maximum = max(blocks)
    blocks = list(set(blocks) - set([maximum]))
    results = []
    for k in range(0, n):
        for left_set in itertools.combinations(blocks, k):
            for left in f(left_set, m - 1):
                rights = itertools.permutations(list(set(blocks) - set(left)))
                for right in rights:
                    results.append(list(left) + [maximum] + list(right))
    return results

def b(n, l, r):
    blocks = range(1, n + 1)
    results = []
    maximum = max(blocks)
    blocks = list(set(blocks) - set([maximum]))
    for k in range(0, n):
        for left_set in itertools.combinations(blocks, k):
            for left in f(left_set, l - 1):
                other = list(set(blocks) - set(left))
                rights = f(other, r - 1)
                for right in rights:
                    results.append(list(left) + [maximum] + list(right))
    return results

# Sample
print b(4, 3, 2) # -> [[1, 2, 4, 3], [1, 3, 4, 2], [2, 3, 4, 1]]

Ответ 5

Получим общее решение F(N, L, R), исследуя конкретный тестовый регистр: F(10, 4, 3).

• Сначала рассмотрим 10 в крайнем левом возможном положении, 4-й ( _ _ _ 10 _ _ _ _ _ _ ).
• Тогда найдем произведение числа допустимых последовательностей слева и справа от 10.
• Далее мы рассмотрим 10 в пятом слоте, вычислим другой продукт и добавим его в предыдущий.
• Этот процесс будет продолжаться до 10 в последнем возможном слоте, восьмом.
• Мы будем использовать переменную с именем pos для отслеживания позиции N.
• Теперь предположим pos = 6 ( _ _ _ _ _ 10 _ _ _ _ ). В левой части 10 расположены 9C5 = (N-1)C(pos-1) множества чисел.
• Поскольку имеет место только порядок этих чисел, мы могли бы посмотреть 1, 2, 3, 4, 5.
• Чтобы построить последовательность с этими числами так, чтобы 3 = L-1 из них были видны слева, мы можем начать с размещения 5 в крайнем левом слоте ( _ _ 5 _ _ ) и следовать аналогичным шагам к тому, что мы делали раньше.
• Итак, если F определяется рекурсивно, его можно использовать здесь.
• Единственное отличие теперь в том, что порядок чисел справа от 5 несуществен.
• Чтобы решить эту проблему, мы будем использовать сигнал INF (бесконечность), для R, чтобы указать его несущественность.
• Поворачивая вправо от 10, осталось 4 = N-pos.
• Сначала рассмотрим 4 в последнем возможном слоте, положение 2 = R-1 справа ( _ _ 4 _ ).
• Здесь то, что появляется в левой части 4, несущественно.
• Но счетные блоки из 4 блоков с простым условием, что 2 из них должны быть видны справа, ничем не отличаются от расчётных аранжировок тех же блоков с простым условием, что 2 из них должны быть видны слева.
  • то есть. вместо подсчета таких последовательностей, как 3 1 4 2, можно подсчитать последовательности, такие как 2 4 1 3
• Таким образом, количество допустимых аранжировок справа от 10 равно F(4, 2, INF).
• Таким образом, число аранжировок при pos == 6 равно 9C5 * F(5, 3, INF) * F(4, 2, INF) = (N-1)C(pos-1) * F(pos-1, L-1, INF)* F(N-pos, R-1, INF).
• Аналогично, в F(5, 3, INF) 5 будет рассмотрен в последовательности слотов с L = 2 и т.д.
• Так как функция вызывает себя при восстановлении L или R, она должна возвращать значение, когда L = 1, то есть F(N, 1, INF) должен быть базовым.
• Теперь рассмотрим компоновку _ _ _ _ _ 6 7 10 _ _.
  • Единственный слот 5 может принимать первый, и следующие 4 слота могут быть заполнены любым способом; таким образом F(5, 1, INF) = 4!.
  • Тогда ясно F(N, 1, INF) = (N-1)!.
  • Другие (тривиальные) базовые случаи и детали можно увидеть в реализации C ниже.

Здесь - ссылка для тестирования кода

#define INF UINT_MAX

long long unsigned fact(unsigned n) { return n ? n * fact(n-1) : 1; }

unsigned C(unsigned n, unsigned k) { return fact(n) / (fact(k) * fact(n-k)); }

unsigned F(unsigned N, unsigned L, unsigned R)
{
    unsigned pos, sum = 0;
    if(R != INF)
    {
        if(L == 0 || R == 0 || N < L || N < R) return 0;
        if(L == 1) return F(N-1, R-1, INF);
        if(R == 1) return F(N-1, L-1, INF);
        for(pos = L; pos <= N-R+1; ++pos)
           sum += C(N-1, pos-1) * F(pos-1, L-1, INF) * F(N-pos, R-1, INF);
    }
    else
    {
        if(L == 1) return fact(N-1);
        for(pos = L; pos <= N; ++pos)
           sum += C(N-1, pos-1) * F(pos-1, L-1, INF) * fact(N-pos);
    }
    return sum;
}