Google采访：块的安排

给你N个高度为1 … N的块。 您可以在多less种方式中排列这些块，使得从左侧看时只能看到L个块（其余块被较高的块遮挡），从右侧看只能看到R个块？ 给定N=3, L=2, R=1例子N=3, L=2, R=1只有一种排列{2, 1, 3}而对于N=3, L=2, R=2 ，有两种方式{1, 3, 2}和{2, 3, 1} 。

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

Answer 1

这是一个计数问题，而不是一个构造问题，所以我们可以使用recursion来处理它。 由于这个问题有两个自然部分，从左边看，右边看，把它分解出来，先解决一部分。

设b(N, L, R)为解的个数，令f(N, L)为N个块的排列数，使得L从左边可见。 首先考虑f因为它更容易。

方法1

让我们得到初始条件，然后进行recursion。 如果所有的都是可见的，那么他们必须越来越有序，所以

 f(N, N) = 1 

如果假设是比可用块更可见的块，那么我们没有办法做到这一点

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

如果只有一个块应该是可见的，然后把最大的，然后其他人可以按照任何顺序，所以

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

最后，recursion考虑最高区块的位置， N表示从左边开始的第k个点。 然后在(N-1 choose k-1)方式中(N-1 choose k-1)前面的块，将这些块Nk左边可见的L-1 ，然后按照你喜欢的顺序将Nk块排列在N之后，给出：

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

事实上，由于对于x<L ， f(x-1,L-1) = 0 ，所以我们也可以从L开始而不是1 ：

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

对，所以现在让我们更容易理解，让我们用f来解决更难的位b 。 同样，使用基于最高块位置的recursion，再次说N在左边的位置k 。 和以前一样，在N-1 choose k-1方式之前select它之前的块，但现在分别考虑该块的每一边。 对于N左边的k-1块，确保它们中的正好L-1是可见的。 对于N右边的Nk块，确保R-1可见，然后颠倒你从f得到的顺序。 所以答案是：

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

f在上面完全解决了。 再一次，许多项将是零，所以我们只想取k使得k-1 >= L-1且Nk >= R-1

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

---

方法2

我再次考虑这个问题，发现一个更好的方法，避免了总和。

如果以相反的方式解决问题，那么就是考虑添加最小的块而不是最大的块，那么f的recursion就变得简单多了。 在这种情况下，在相同的初始条件下，复发是

 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保持固定）。

这种recursion的优点是总是减lessN ，尽pipe它使得看到一些公式更加困难，例如f(N,N-1) = (N choose 2) 。 这个公式很容易从前面的公式中显示出来，尽pipe我不确定如何从这个更简单的recursion中很好的推导出它。

现在，为了回到原来的问题和解决b ，我们也可以采取不同的方法。 除了之前的总和之外，还可以将可见块视为数据包，因此，如果从左侧可见一个块，则其数据包由其右侧的所有块组成，并且在从左侧可见的下一个块的前面。类似地，如果一个块从右边可见，那么它的数据包包含它所有的块，直到从右边可见的下一个块。 除了最高的街区之外，为所有人做这个。 这使得L+R数据包。 给定数据包，只需通过反转块的顺序即可从左侧移动到右侧。 因此，一般情况b(N,L,R)实际上简化为求解情况b(N,L,1) = f(N,L) ，然后select哪些数据包放在左边，哪些放在右边。 所以我们有

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

再说一遍，这个配方比以前的版本有一些优势。 把这两个公式放在一起，可以更容易地看到整个问题的复杂性。 不过，我仍然更喜欢第一种方法来构build解决scheme，但也许其他人会不同意。 总而言之，只是表明有不止一个好办法来解决这个问题。

---

什么是斯特林数字？

正如Jason所指出的那样， f(N,L)数正好是第一类的（无符号） 斯特林数 。 我们可以立即从recursion公式中看到这一点。 然而，能够直接看到它总是很好的，所以在这里。

表示为S(N,L)的第一types的（无符号）斯特林数目计数N到L个周期的排列数目。 给定以循环表示法写的置换，我们通过以该循环中的最大数字开始循环，然后以循环的第一个数字逐渐sorting循环，以规范forms编写置换。 例如，排列

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

会以规范forms写成

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

现在放下圆括号，注意如果这些是块的高度，那么左边的可见块数就是周期数！ 这是因为每个循环的第一个数字会阻止循环中的所有其他数字，每个循环的第一个数字在前一个循环后面是可见的。 因此，这个问题实际上只是一个偷偷摸摸的方法来要求你find一个斯特林数的公式。

Answer 2

那么，就像小N的经验性解决scheme一样：

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个块的行/列的总和：即在@PenOne的符号中，

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

• 每个对angular线都是一排帕斯卡三angular形，这个对angular线的常数系数K乘以 – 我不能certificate这一点，但我确信有人可以 – 即：

  b(N,L,R) = K * (L+R-2 choose L-1)其中K = b(N,1,L+R-1)

所以计算b（N，L，R）的计算复杂度与计算每个三angular形第一列（或行）的b（N，1，L + R-1）的计算复杂度相同。

这个观察可能是明确解决scheme的95％（其他5％，我确定涉及标准的组合身份，我不太熟悉这些）。

---

用整数序列的在线百科全书快速检查显示b（N，1，R）看起来是OEIS序列A094638 ：

（n，k）= | s（n，n + 1-k）|，其中s（n，k）是第一类有符号斯特林数（1 <= k <= n ;换句话说，第一类的无符号斯特林数以相反的顺序）。 1,1,1,1,3,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,27,29,29,23,23,24,25,27,27,28,29,23,23,24,25,27,28,29,23,23,23,23,24,25,27,28,29,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,24,25,29,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,24,25,29,23,22,22,22,23 1664,1764,720,1,28,322,1906,6769,13132,13068,5040,1,36,546,4536,22449，67284,118124,109584,40320,1,45,870,9450,63273，以及其中所述的氨基酸序列与SEQ ID NO： 269325，723680，1172700

至于如何有效地计算第一类斯特林数 ，我不确定; 维基百科给出了一个明确的公式，但它看起来像一个讨厌的总和。 这个问题（计算第一类Stirling＃） 出现在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(Nk, 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(Nk); } return acc; } } function comb(n, k) { return fact(n) / (fact(k) * fact(nk)); } 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

这是我的build设解决scheme，灵感来自@PenOne的想法。

 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

我们通过检查一个特定的testing用例来得到一个通用解F(N, L, R) ： F(10, 4, 3) 10,4,3 F(10, 4, 3) 。

1. 我们首先考虑十个最左边的位置，第四个( _ _ _ 10 _ _ _ _ _ _ ) 。
2. 然后我们find左边和右边有效序列数的乘积。
3. 接下来，我们将在第5个槽中考虑10个，计算另一个产品并将其添加到前一个。
4. 这个过程将持续到最后一个可能的时间点，即8点。
5. 我们将使用名为pos的variables来跟踪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是recursion定义的，可以在这里使用。
10. 现在唯一的区别是5号右边的数字的顺序是不重要的。
11. 为了解决这个问题，我们将使用一个INF（infinity）的信号来表示它不重要的地方。
12. 转到10的右边，会有4 = N-pos数字。
13. 我们首先在最后一个可能的时隙中考虑4，从右边的位置2 = R-1 ( _ _ 4 _ ) 。
14. 这里出现在4的左边是无关紧要的。
15. 但是，从右边数2条应该是可见的条件来计算4个街区的安排，与仅仅从左边可见的情况下计算相同街区的安排没有区别。
    • 即。 而不是像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减less，当L = 1时它必须返回一个值，即F(N, 1, INF)必须是基本情况。
20. 现在考虑一下安排_ _ _ _ _ 6 7 10 _ _ 。
    • 唯一的5号插槽可以是第一个，以下4个插槽可以任何方式填充; 因此F(5, 1, INF) = 4! 。
    • 那么显然F(N, 1, INF) = (N-1)! 。
    • 其他（微不足道的）基本情况和细节可以在下面的C实现中看到。

这里是testing代码的链接

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