用Python高效生成词典序列

Aman_X • 4 年前 • 785 次点击

我想生成一个数字的字典序列,这样每个数字的数字和就是一个给定的常数。它有点类似于“子集和问题”。例如,如果我希望生成总和为3的4位数字,那么我有一个类似的序列:

[3 0 0 0]

[2 1 0 0]

[2 0 1 0]

[2 0 0 1]

我在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上。我怎样才能使我的代码更有效率,或者有更好的方法来编码它?

Python社区是高质量的Python/Django开发社区
本文地址：http://www.python88.com/topic/55836

785 次点击

文章 [ 4 ] | 最新文章 4 年前

• 1 楼

Aman_X 4 年前

https://bugs.python.org/msg144273 ). 代码如下:

import itertools
import operator

def combinations_with_replacement(iterable, r):
    # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
    pool = tuple(iterable)
    n = len(pool)
    if not n and r:
        return
    indices = [0] * r
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != n - 1:
                break
        else:
            return
        indices[i:] = [indices[i] + 1] * (r - i)
        yield tuple(pool[i] for i in indices)

int_part = lambda n, k: (tuple(map(c.count, range(k))) for c in combinations_with_replacement(range(k), n))
for item in int_part(3,4): print(item)

• 2 楼

Shoyeb Sheikh 5 年前

我有一个更好的解决方案,使用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)

enter image description here

enter link description here

但对于n=100和s=6,这段代码需要时间来完成所有的组合,我认为计算结果需要几天的时间。

• 3 楼

pkfm 5 年前

我的建议:

yield ,而不是在每次迭代时连接全局变量的循环。
保持一个连续和,而不是计算数字数组表示的某个子集的和。

注:没有特别的顺序暗示。

• 4 楼

MBo 5 年前

非常有效的算法改编自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

登录后回复