谷歌面试：块的配置 [英] Google Interview: Arrangement of Blocks
问题描述
正在给身高1 ... N的N块。有多少种方法，你可以安排这些块在一排从左边看时，你看到的只是L个块（其余是隐藏的高块），并从右侧看到的，当你看到那么仅仅红色块来？例如给予 N = 3，L = 2，R = 1 只有一个安排 {2，1，3} 而对于 N = 3，L = 2，R = 2 有两种方法 {1，3，2} 和 {2，3，1} 。
You are given N blocks of height 1…N. In how many ways can you arrange these blocks in a row such that when viewed from left you see only L blocks (rest are hidden by taller blocks) and when seen from right you see only R blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3} while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.
我们应该如何解决这个问题，通过编程吗？任何有效的方式？
How should we solve this problem by programming? Any efficient ways?
推荐答案
这是一个计算问题，而不是建设的问题，所以我们可以使用递归接近它。由于该问题有两个天然部分，从左边看，看着从右侧，打破它，解决的只是其中的一部分先。
This is a counting problem, not a construction problem, so we can approach it using recursion. Since the problem has two natural parts, looking from the left and looking from the right, break it up and solve for just one part first.
让 B（N，L，R）是解决方案的数量，并让 F（N，L）是的 N 块安排的数量，以便→是从左边可见。先想想 F ，因为它更容易。
Let b(N, L, R) be the number of solutions, and let f(N, L) be the number of arrangements of N blocks so that L are visible from the left. First think about f because it's easier.
方法1 的
APPROACH 1
让我们的初始条件，然后去递归。如果所有都是可见的，那么它们必须日益有序的，所以
Let's get the initial conditions and then go for recursion. If all are to be visible, then they must be ordered increasingly, so
f(N, N) = 1
如果有想比可用块更明显的块，再没有什么可以做，所以
If there are suppose to be more visible blocks than available blocks, then nothing we can do, so
f(N, M) = 0 if N < M
如果只有一个街区应该是可见的，然后把最大的第一，然后其他人可以以任意顺序可循，所以
If only one block should be visible, then put the largest first and then the others can follow in any order, so
f(N,1) = (N-1)!
最后，递归，想想最高的块的位置，说 N 是 K 日现货从左边。然后选择块才进来（N-1选择k-1）的方式，安排那些块，以便准确地 L-1 是从左边可见的，责令<$ C $ C> NK 背后 N 它在任何你喜欢的块，捐赠：
Finally, for the recursion, think about the position of the tallest block, say N is in the kth spot from the left. Then choose the blocks to come before it in (N-1 choose k-1) ways, arrange those blocks so that exactly L-1 are visible from the left, and order the N-k blocks behind N it in any you like, giving:
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 1
In fact, since f(x-1,L-1) = 0 for x<L, we may as well start k at L instead of 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选择k-1 的方式，但现在想想块的每个侧面分开。对于 K-1 的 N 留块，确保准确地 L-1 是可见的。对于 NK 块右 N ，确保 R-1 是可见的，然后颠倒顺序，你会得到从 F 。所以答案是：
Right, so now that the easier bit is understood, let's use f to solve for the harder bit b. Again, use recursion based on the position of the tallest block, again say N is in position k from the left. As before, choose the blocks before it in N-1 choose k-1 ways, but now think about each side of that block separately. For the k-1 blocks left of N, make sure that exactly L-1 of them are visible. For the N-k blocks right of N, make sure that R-1 are visible and then reverse the order you would get from f. Therefore the answer is:
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＆GT; = L-1 和 NK＆GT; = R-1 获得
where f is completely worked out above. Again, many terms will be zero, so we only want to take k such that k-1 >= L-1 and N-k >= R-1 to get
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 的
APPROACH 2
我想过这个问题又来了，发现有些更好的办法，避免了总结。
I thought about this problem again and found a somewhat nicer approach that avoids the summation.
如果你的工作问题了相反的方向，即认为将最大块的小块来代替，那么复发的 F 变得简单多了。在这种情况下，用相同的初始条件，复发是
If you work the problem the opposite way, that is think of adding the smallest block instead of the largest block, then the recurrence for f becomes much simpler. In this case, with the same initial conditions, the recurrence is
f(N,L) = f(N-1,L-1) + (N-1) * f(N-1,L)
其中第一项， F（N-1，L-1），来自放置小块在最左边的位置，从而增加多了一个可见的块（因此，→降低到 L-1 ），和第二项，（N-1 ）* F（N-1，L），占投入最小的块中的任何 N-1 非面前立场，在这种情况下，它是不可见的（因此→维持不变）。
where the first term, f(N-1,L-1), comes from placing the smallest block in the leftmost position, thereby adding one more visible block (hence L decreases to L-1), and the second term, (N-1) * f(N-1,L), accounts for putting the smallest block in any of the N-1 non-front positions, in which case it is not visible (hence L stays fixed).
这递归具有总是减小的优势 N ，虽然使之更难以看到一些公式，例如 F（N，N- -1）=（N选择2）。这个公式是相当容易从previous公式来证明，虽然我不能确定如何很好地从这个简单的复发得到它。
This recursion has the advantage of always decreasing N, though it makes it more difficult to see some formulas, for example f(N,N-1) = (N choose 2). This formula is fairly easy to show from the previous formula, though I'm not certain how to derive it nicely from this simpler recurrence.
现在，要回到原来的问题，解决了 B ，我们也可以采取不同的方法。求和之前而不是，想到的可见块作为进来的报文，因此，如果一个块是可见的，从左侧，则其包由权利，并在接下来的块从左侧可见前面所有块的，并同样地，如果一个块是从右侧可见那么其数据包中包含有留到下一个块从右侧可见的所有块。做到这一点的所有，但最高的区块。这使得 L + R 包。定的报文，可以简单地通过反转块的顺序移动一个从左侧到右侧。因此一般情况下 B（N，L，R）的实际上降低到解决的情况下 B（N，L，1）= F（N， L）的然后选择这些包的穿上右边的左边和哪个。因此，我们有
Now, to get back to the original problem and solve for b, we can also take a different approach. Instead of the summation before, think of the visible blocks as coming in packets, so that if a block is visible from the left, then its packet consists of all blocks right of it and in front of the next block visible from the left, and similarly if a block is visible from the right then its packet contains all blocks left of it until the next block visible from the right. Do this for all but the tallest block. This makes for L+R packets. Given the packets, you can move one from the left side to the right side simply by reversing the order of the blocks. Therefore the general case b(N,L,R) actually reduces to solving the case b(N,L,1) = f(N,L) and then choosing which of the packets to put on the left and which on the right. Therefore we have
b(N,L,R) = (L+R choose L) * f(N,L+R)
此外，这个改写有一定的优势超过了previous版本。把后两个公式放在一起，它更容易看到整个问题的复杂性。但是，我还是preFER构建解决方案，第一种方法，但也许其他人会不同意。总而言之，这只是表明有来处理这个问题不止一个好办法。
Again, this reformulation has some advantages over the previous version. Putting these latter two formulas together, it's much easier to see the complexity of the overall problem. However, I still prefer the first approach for constructing solutions, though perhaps others will disagree. All in all it just goes to show there's more than one good way to approach the problem.
什么是与Stirling数？的
What's with the Stirling numbers?
由于贾森指出， F（N，L）数字是precisely的（无符号）的第一种 Stirling数。人们可以从递推公式为每个马上看到这一点。然而，它总是很高兴能够直接看到它，所以这里去。
As Jason points out, the f(N,L) numbers are precisely the (unsigned) Stirling numbers of the first kind. One can see this immediately from the recursive formulas for each. However, it's always nice to be able to see it directly, so here goes.
第一类，记 S（N，L）的（无符号）Stirling数计数ñ排列的数量到→周期。由于写周期符号置换，我们写在规范的形式排列由开始的周期数最多的那个周期，然后由循环的第一个数字越来越订货周期。例如，所述置换
The (unsigned) Stirling numbers of the First Kind, denoted S(N,L) count the number of permutations of N into L cycles. Given a permutation written in cycle notation, we write the permutation in canonical form by beginning the cycle with the largest number in that cycle and then ordering the cycles increasingly by the first number of the cycle. For example, the permutation
(2 6) (5 1 4) (3 7)
将被写入规范形式为
would be written in canonical form as
(5 1 4) (6 2) (7 3)
现在删除括号并注意到，如果这些是块的高度，那么从左侧可见块的数目是完全的周期数！这是因为，第一数量的每个循环阻止所有其它数量的周期，并且在每个连续周期的第一个数字是previous周期后面可见。因此，这个问题实际上只是偷偷摸摸地问你找到Stirling数的公式。
Now drop the parentheses and notice that if these are the heights of the blocks, then the number of visible blocks from the left is exactly the number of cycles! This is because the first number of each cycle blocks all other numbers in the cycle, and the first number of each successive cycle is visible behind the previous cycle. Hence this problem is really just a sneaky way to ask you to find a formula for Stirling numbers.
这篇关于谷歌面试：块的配置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
