谷歌采访:区块的排列

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点。然后以(N-1 choose k-1)的方式选择它前面的块，排列这些块，以便从左侧完全可以看到L-1，并按您喜欢的任何顺序对N后面的N-k块进行排序，给出：

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

事实上，由于x<L的f(x-1,L-1) = 0，我们不妨从L开始k，而不是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的方式选择它前面的块，但现在分别考虑该块的每一面。对于N左侧的k-1块，确保其中的L-1是可见的。对于N右侧的N-k块，请确保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)

同样，这种重新制定与以前的版本相比具有一些优势。将后两个公式放在一起，更容易看出整个问题的复杂性。然而，我仍然更喜欢构建解决方案的第一种方法，尽管其他人可能不同意。总而言之，这表明有不止一种好的方法来解决这个问题。

斯特林数是怎么回事？

正如Jason所指出的，f(N,L)数字就是(无符号的) Stirling numbers of the first kind。人们可以直接从each的递归公式中看到这一点。然而，能够直接看到它总是很好的，所以这里是这样的。

表示为S(N,L)的第一类(无符号) Stirling数计算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计数)
• if p是N-1个块的排列，并且有计数(Lp，Rp)，那么插入在每个可能的点中的块N的N个排列可以具有从L=1到Lp+1的计数，并且R=1到Rp +1。

从经验输出中：

具有N个块的最左边的列或最上面的行(其中L=1或R= 1)是具有N-1个块的行/列的总和:即，在@

• 的符号中，

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

• Each对角线是一排帕斯卡三角形，乘以该对角线的常数K --我不能证明这一点，但我相信有人可以--例如：

b(N,L,R) = K * (L+R-2 choose L-1) where 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 sequence A094638

A094638三角形按行读取: T(n，k) =|s(n，n+1- k) |，其中s(n，k)是第一类有符号Stirling数(1<=k<=n；换句话说，按逆序排列的第一类无符号Stirling数)。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

至于如何有效地计算Stirling numbers of the first kind，我不确定；维基百科给出了一个明确的公式，但它看起来像是一个令人讨厌的总和。这个问题(计算第一类Stirling #s ) shows up on MathOverflow，它看起来像O(n^2)，正如PengOne假设。

Answer 3

基于@PengOne的回答，这里是my Javascript implementation

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