Ter*_* Li 40 language-agnostic algorithm combinatorics
给你N块高度1 ... N. 您可以通过多少种方式将这些块排成一排,这样当从左侧看时,您只能看到L个块(其余部分被较高的块隐藏),从右侧看时您只看到R块？给出的例子N=3, L=2, R=1只有一种安排,{2, 1, 3}而N=3, L=2, R=2有两种方式{1, 3, 2}和{2, 3, 1}.
我们应该如何通过编程解决这个问题？任何有效的方法？
Pen*_*One 48
这是一个计数问题,而不是构造问题,所以我们可以使用递归来处理它.由于问题有两个自然部分,从左侧看并从右侧看,将其分解并首先解决一个部分.
让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从左边个点.然后选择要在其前面的块(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)
同样,这种重新制定比以前的版本有一些优势.将后两个公式放在一起,可以更容易地看到整体问题的复杂性.但是,我仍然更喜欢构建解决方案的第一种方法,尽管其他人可能不同意.总而言之,它只是表明解决问题的方法不止一种.
什么是斯特林数字？
正如杰森所指出的那样,这些f(N,L)数字恰恰是第一种斯特林的(无符号)数字.人们可以从每个的递归公式中立即看到这一点.但是,能够直接看到它总是很好,所以这里.
第一类的(无符号)斯特林数表示S(N,L)为N进入L循环的排列数.给定以循环符号写入的排列,我们以规范形式编写排列,通过在该循环中以最大数字开始循环,然后逐渐按循环的第一个数字排序循环.例如,排列
(2 6) (5 1 4) (3 7)
将以规范形式书写为
(5 1 4) (6 2) (7 3)
现在放下括号,注意如果这些是块的高度,那么左边可见块的数量就是周期数!这是因为每个循环的第一个数字会阻止循环中的所有其他数字,并且每个连续循环的第一个数字在前一个循环后面可见.因此,这个问题实际上只是一种偷偷摸摸的方式,要求您找到斯特林数字的公式.
Jas*_*n S 10
好吧,就像小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
你会在问题陈述中注意到一些显而易见的(很明显的,很明显的)事情:
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
每个对角线都是一排帕斯卡的三角形,乘以该对角线的常数因子K - 我无法证明这一点,但我确信有人可以 - 即:
b(N,L,R) = K * (L+R-2 choose L-1) 哪里 K = b(N,1,L+R-1)
因此,计算b(N,L,R)的计算复杂度与计算b(N,1,L + R-1)的计算复杂度相同,b是每个三角形中的第一列(或行).
这个观察结果可能是显性解决方案的95%(另外5%我肯定涉及标准的组合身份,我不太熟悉那些).
使用在线整数序列百科全书快速检查显示b(N,1,R)似乎是OEIS序列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,1,1,15,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,1172900
至于如何有效地计算第一类斯特林数,我不确定; 维基百科给出了一个明确的公式,但它看起来像一个讨厌的总和.这个问题(计算第一种斯特林#s)出现在MathOverflow上,看起来像O(n ^ 2),正如PengOne所假设的那样.
基于@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()));
});