MBo

非常有效的算法改编自Jorg Arndt的书“计算问题”
(第章 7.2 Co-lexicographic order for compositions into exactly k parts )

n = 4
k = 3

x = [0] * n
x[0] = k

while True:
    print(x)
    v = x[-1]
    if (k==v ):
        break
    x[-1] = 0
    j = -2
    while (0==x[j]):
        j -= 1
    x[j] -= 1
    x[j+1] = 1 + v

[3, 0, 0, 0]
[2, 1, 0, 0]
[2, 0, 1, 0]
[2, 0, 0, 1]
[1, 2, 0, 0]
[1, 1, 1, 0]
[1, 1, 0, 1]
[1, 0, 2, 0]
[1, 0, 1, 1]
[1, 0, 0, 2]
[0, 3, 0, 0]
[0, 2, 1, 0]
[0, 2, 0, 1]
[0, 1, 2, 0]
[0, 1, 1, 1]
[0, 1, 0, 2]
[0, 0, 3, 0]
[0, 0, 2, 1]
[0, 0, 1, 2]
[0, 0, 0, 3]

对于n=100,k=2,3,4,5(2.8ghz Cel-1840),普通Python(可能numpy数组更快)的合成次数和时间(秒)

2  5050 0.040000200271606445
3  171700 0.9900014400482178
4  4421275 20.02204465866089
5  91962520 372.03577995300293
I expect time  2 hours for 100/6 generation

x = np.zeros((n,), dtype=int) )给予 更糟的

2  5050 0.07999992370605469
3  171700 2.390003204345703
4  4421275 54.74532389640808

本地代码(这是Delphi,C/C++编译器可能会更好地优化)生成100/6 21秒后

3  171700  0.012
4  4421275  0.125
5  91962520  1.544
6  1609344100 20.748

MSVS VC++: 18秒 ! (氧气优化)

5  91962520 1.466
6  1609344100 18.283

所以每秒有1亿个变种。 检查空单元格会浪费很多时间(因为填充率很小)。Arndt所描述的速度是在较高的k/n比下达到的,约为每秒3-5亿个变量:

n=25, k=15 25140840660 60.981  400 millions per second

对于灰度图像,圆半径应与反向亮度的平方根成比例(如果忽略过大的效果)

R = Coeff * CellSize * Sqrt((255 - Brightness)/255)  
//or Sqrt(1.0- Brightness)  for 0..1 range
//Coeff = 1/2 gives 2R=CellSize for dark with fill degree about 0.76

代码打印序列的位置和长度:

s = 'TCAAAAACCABBBT'
start = 0
for i in range(1, len(s) + 1):
    if (i==len(s) or s[i] != s[i-1]):
        if (i - start > 1):
            print(start, i - start)
        start = i
>>2 5
7 2
10 3