在Python中有效地生成词典系列

Question

我想生成一个词典系列的数字，这样对于每个数字，数字的总和是给定的常数。它有点类似于“子集和问题”。例如，如果我希望生成sum = 3的4位数字，那么我有一个类似的系列：

[3 0 0 0]

[2 1 0 0]

[2 0 1 0]

[2 0 0 1]

[1 2 0 0] ......等等。

我能够使用以下代码在Python中成功完成：

import numpy as np

M = 4 # No. of digits
N = 3 # Target sum

a = np.zeros((1,M), int)
b = np.zeros((1,M), int)

a[0][0] = N
jj = 0

while a[jj][M-1] != N:
    ii = M-2
    while a[jj][ii] == 0:
          ii = ii-1
    kk = ii
    if kk > 0:
       b[0][0:kk-1] = a[jj][0:kk-1]
    b[0][kk] = a[jj][kk]-1
    b[0][kk+1] = N - sum(b[0][0:kk+1])
    b[0][kk+2:] = 0
    a = np.concatenate((a,b), axis=0)
    jj += 1

for ii in range(0,len(a)):
    print a[ii]

print len(a)

我不认为这是一种非常有效的方式（因为我是一个Python新手）。它适用于M和N（<10）的小值，但实际上很慢。我希望将它用于M~100和N~6。如何使我的代码更高效或是否有更好的编码方式？

Answer 1

非常有效的算法改编自Jorg Arndt书“Matters Computational” （章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.8 ghz 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

与numpy数组（x = np.zeros((n,), dtype=int)）相同会产生更糟糕的结果 - 但也许是因为我不知道如何正确使用它们

2  5050 0.07999992370605469
3  171700 2.390003204345703
4  4421275 54.74532389640808

本机代码（这是Delphi，C / C ++编译器可能更好地优化）在21秒内生成100/6

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

在没有完成所有测量之前无法入睡:)

MSVS VC ++：18秒！ （O2优化）

5  91962520 1.466
6  1609344100 18.283

所以每秒有100万个变种。检查空单元格浪费了很多时间（因为填充率很小）。 Arndt描述的速度在更高的k / n比率下达到，并且每秒约300-500百万个变体：

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

Answer 2

我的建议：

1. 使用yield将其重写为生成器，而不是在每次迭代时连接全局变量的循环。
2. 保持运行总和而不是计算数字的数组表示的某个子集的总和。
3. 在您的工作号表示的单个实例上操作，而不是在每次迭代时将其副本拼接到临时变量。

注意没有暗示特定的顺序。

Answer 3

我有一个更好的解决方案，使用itertools如下，

from itertools import product
n = 4 #number of elements
s = 3 #sum of elements
r = []
for x in range(n):
    r.append(x)
result = [p for p in product(r, repeat=n) if sum(p) == s]
print(len(result))
print(result)

我说这更好，因为我的系统需要0.1秒，而你的numpy代码需要0.2秒。

但是，只要n = 100和s = 6，这段代码需要时间来完成所有组合，我认为计算结果需要数天时间。