谷歌面试：块的排列顺序

Question

谷歌面试：块的排列顺序

46

你将得到高度为1到N的N个方块。你能以多少种方式将这些方块排成一行，使从左侧看只能看到L个方块（其他被更高的方块遮盖），而从右侧看只能看到R个方块？例如：N=3, L=2, R=1，只有一种安排{2, 1, 3}，而对于N=3, L=2, R=2，有两种方法{1, 3, 2}和{2, 3, 1}。

我们应该如何通过编程解决这个问题？有什么有效的方法吗？

- Terry Li

第一个例子应该是 {1,2,3} 而不是 {2,1,3}。 - Cratylus

2

@user384706 一点也不。{1,2,3} 从左边看有 3 个可见块，从右边看有 1 个可见块。 - PengOne

@user384706 不是的，如果 {1,2,3} 是 L，则 L 的长度为 3。 - daniloquio

@user384706 我猜你忘记数第一个了。 - Terry Li

4

从左边看{2,1,3}，你会看到高度为2的方块和高度为3的方块，但是不会看到高度为1的方块，因为它被高度为2的方块挡住了。 - PengOne

显示剩余2条评论

5个回答

11

好的，针对小 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。

从经验输出中可以看出：

具有N个块的最左侧列或最顶部行（其中L = 1或R = 1）是具有N-1个块的行/列之和：即在@PengOne的符号中，

b（N，1，R）= sum（b（N-1，k，R-1）for k = 1 to N-R+1
每个对角线都是Pascal三角形的一行，乘以该对角线的常数因子K-我不能证明这一点，但我确信有人可以-即：

b（N，L，R）= K *（L+R-2选择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 sequence 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

关于如何高效计算第一类斯特林数, 我不确定；维基百科给出了一个明确的公式，但看起来像是一个恶心的求和。这个问题（计算第一类斯特林数）在MathOverflow上出现，看起来像O(n^2)，正如PengOne所猜测的那样。

- Jason S

你对对角线的观察可以从我上面给出的公式中得出。 - PengOne

2

我对组合代数一窍不通，所以这方面就得听你的了。 :-) - Jason S

@JasonS +1 因为你的诚实。我没有勇气承认它。现在我有了。谢谢。 - Terry Li

+1 对于额外的研究表示赞赏。虽然我更倾向于数学家而非程序员，但我认为两种类型都很有用 :-) - PengOne

@JasonS@PengOne 理论和实践结合才能得出好的答案！ - Terry Li

5

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

- Ivan

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

- Valentin Shergin

1

我们通过检查一个特定的测试用例：F(10, 4, 3)，得出一个通用解决方案F(N, L, R)。

我们首先考虑10在最左边的位置，即第4个位置 ( _ _ _ 10 _ _ _ _ _ _ )。
然后我们计算左侧和右侧有效序列的乘积。
接下来，我们将考虑10在第5个位置，计算另一个乘积并将其添加到前一个乘积中。
这个过程将一直持续到10在最后一个位置，即第8个位置。
我们将使用名为pos的变量来跟踪N的位置。
现在假设pos = 6 ( _ _ _ _ _ 10 _ _ _ _ )。在10的左侧，有9C5 = (N-1)C(pos-1)组数字需要排列。
由于只有这些数字的顺序很重要，我们可以看作是1、2、3、4、5。
为了构造一个序列，使得其中3个数字从左侧可见，我们可以将5放在最左侧的位置( _ _ 5 _ _ )，并按照之前所做的类似步骤进行。
因此，如果F被递归地定义，它可以在这里使用。
现在唯一的区别是，在5的右侧，数字的顺序并不重要。
为了解决这个问题，我们将使用一个信号INF（无限大）来表示R的不重要性。
转向10的右侧，还剩下4 = N-pos个数字。
我们首先考虑4在最后一个位置，即从右侧数第2个位置 ( _ _ 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)!。

其他（微不足道

这里是一个用于测试代码的链接

#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;
}

- Apshir

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- PengOne · Accepted Answer

这是一个计数问题，而不是构造问题，因此我们可以使用递归方法来解决。由于问题有两个自然部分，从左边看和从右边看，将其分开并先解决其中一个部分。

让b（N，L，R）为方案数量，f（N，L）为在左侧可见的N块的排列数量。首先考虑f，因为它更容易。 方法一 让我们获取初始条件，然后进行递归。如果所有块都要可见，则它们必须按递增顺序排列，因此：

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-k块按任意顺序放在N的后面：

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 开始而不是从 1 开始进行 k：

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)

再次，这种重新表述相对于先前的版本有一些优点。将后两个公式结合起来，更容易看出整个问题的复杂性。然而，我仍然更喜欢第一种方法来构建解决方案，尽管可能会有人持不同意见。总体而言，这表明了解决问题的好方法不止一种。

Stirling数是什么？

正如Jason指出的那样，f(N, L)数恰好是（无符号的）第一类斯特林数。可以立即从每个递归公式中看到这一点。然而，直接看到它总是很好的，下面就是详细说明。

第一类斯特林数（unsigned Stirling numbers of the First Kind）用S(N, L)表示，计算将N排成L个环的置换数量。通过在循环符号中写出置换，通过将循环以循环中最大的数字开头并按照循环中的第一个数字按升序排序来编写规范形式的置换。例如，置换

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

按规范形式编写的内容如下：

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

现在删除括号，并注意如果这些是块的高度，则从左侧可见的块数恰好等于循环数！这是因为每个周期的第一个数字会阻挡该周期中的其他数字，并且每个连续周期的第一个数字可见于前一个周期之后。因此，这个问题实际上只是想让你找到斯特林数的公式的一种巧妙方式。