Google Интервью: расположение блоков

Question

Вам дано N блоков высотой 1… N. Сколько способов вы можете расположить эти блоки в ряд таким образом, чтобы при просмотре слева вы видели только L блоков (остальные скрыты более высокими блоками), а если смотреть справа, вы видите только R блоков? В приведенном примере N=3, L=2, R=1 есть только одна договоренность {2, 1, 3}, в то время как для N=3, L=2, R=2 есть два способа {1, 3, 2} и {2, 3, 1}.

Как мы должны решить эту проблему с помощью программирования? Есть ли эффективные способы?

Answer 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 -ом месте слева. Затем выберите блоки, которые должны стоять перед ним, 1027 * способами, расположите эти блоки так, чтобы ровно 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 слева. Как и прежде, выберите блоки перед ним 1046 * способами, но теперь подумайте о каждой стороне этого блока отдельно. Для 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)

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

Answer 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 для этой диагонали - я не могу это доказать, но я уверен, что кто-то может - т.е.

  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%, я уверен, включают стандартные комбинаторные тождества, я не слишком знаком с ними). ​​

---

Быстрая проверка с помощью Онлайн-энциклопедии целочисленных последовательностей показывает, что 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, 735, 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 </p>

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

Answer 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()));
});

Answer 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]]

Answer 5

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

1. Сначала рассмотрим 10 в крайнем левом положении, 4-е ( _ _ _ 10 _ _ _ _ _ _ ).
2. Затем мы находим произведение числа действительных последовательностей слева и справа от 10.
3. Далее мы рассмотрим 10 в 5-м слоте, вычислим другой продукт и добавим его к предыдущему.
4. Этот процесс будет продолжаться до тех пор, пока 10 не окажется в последнем возможном интервале, 8-м.
5. Мы будем использовать переменную с именем pos, чтобы отслеживать положение N.
6. Теперь предположим, pos = 6 ( _ _ _ _ _ 10 _ _ _ _ ). Слева от 10 есть 9C5 = (N-1)C(pos-1) наборов чисел, которые нужно упорядочить.
7. Поскольку имеет значение только порядок этих чисел, мы могли бы взглянуть на 1, 2, 3, 4, 5.
8. Чтобы построить последовательность с этими числами так, чтобы 3 = L-1 из них были видны слева, мы можем начать с помещения 5 в крайнее левое возможное место ( _ _ 5 _ _ ) и выполнить шаги, аналогичные тем, которые мы делали ранее.
9. Так что, если бы F был определен рекурсивно, его можно было бы использовать здесь.
10. Единственная разница в том, что порядок чисел справа от 5 не имеет значения.
11. Чтобы решить эту проблему, мы будем использовать сигнал INF (бесконечность), чтобы R указывал на его неважность.
12. Повернув направо от 10, останется 4 = N-чисел слева.
13. Сначала рассмотрим 4 в последнем возможном интервале, позиция 2 = R-1 справа ( _ _ 4 _ ).
14. Здесь то, что появляется слева от 4, не имеет значения.
15. Но подсчет расположения 4 блоков с простым условием, что 2 из них должны быть видны справа, ничем не отличается от подсчета расположения тех же блоков с простым условием, что 2 из них должны быть видны слева.
    • т. вместо того, чтобы считать последовательности как 3 1 4 2, можно считать последовательности как 2 4 1 3
16. Таким образом, число действительных соглашений в праве 10 равно F(4, 2, INF).
17. Таким образом, количество аранжировок, когда 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).
18. Аналогично, в F(5, 3, INF) 5 будет рассматриваться в последовательности слотов с L = 2 и т. Д.
19. Поскольку функция вызывает себя с уменьшенным L или R, она должна вернуть значение, когда L = 1, то есть F(N, 1, INF) должно быть базовым регистром.
20. Теперь рассмотрим расположение _ _ _ _ _ 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;
}