### 5 Solutions collect form web for “Google采访：块的安排”

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

` `f(N, N) = 1` `

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

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

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

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

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

` `f(N,L) = f(N-1,L-1) + (N-1) * f(N-1,L)` `

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

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

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

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

（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

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

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

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实现中看到。

` `#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; }` `
• 代表和解决迷宫的形象
• 有没有一种方法来衡量一个列表如何sorting？
• 在Python中，从列表中删除重复项的最快algorithm是什么，以便所有元素都是唯一的*，同时保持顺序*？
• 什么是目前最安全的单向encryptionalgorithm？
• 有向未加权图中最长的非循环path
• 如何旋转matrix90度，而不使用任何额外的空间？
• find第n个排列而不计算其他排列
• 什么是最快/最有效的方法来find一个整数在C中的最高设置位（MSB）？
• 检查一个拼写的数字是否在C ++的范围内
• 可见光谱的RGB值
• 计算两点之间的最短路线