algorithm - Google面试: block 的排列

Question

你得到了N个高度为1…N的块。你可以用多少种方法将这些块排列成一行，这样当你从左边看时，你只看到L个块（其余的块被更高的块隐藏），当你从右边看时，你只看到R个块举例来说，N=3, L=2, R=1只有一种排列方式，{2, 1, 3}有两种方式。
我们应该如何通过编程来解决这个问题有什么有效的方法吗？

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第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)

同样，这一重新制定的版本比以前的版本有一些优势把后两个公式放在一起，就更容易看到整个问题的复杂性。然而，我仍然更喜欢第一种方法来构建解决方案，尽管也许其他人会不同意总的来说，它只是表明有不止一个好的方法来解决这个问题。
斯特林数字是怎么回事？
正如jason指出的， f(N,L)数字正是（无符号的） 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)

现在放下圆括号，注意如果这些是块的高度，那么从左边可见的块的数量就是循环的数量！这是因为每个循环的第一个数字会阻塞循环中的所有其他数字，并且每个连续循环的第一个数字在前一个循环之后可见。因此，这个问题其实只是一个狡猾的方式，要求你找到一个公式斯特林数。