用于整数分区的优雅Python代码
我试图编写代码来解决标准的整数分区问题（ Wikipedia ）。 我写的代码是一团糟。 我需要一个优雅的解决scheme来解决这个问题，因为我想改善我的编码风格。 这不是一个家庭作业问题。
虽然这个答案是好的，我build议skovorodkin的答案如下：
>>> def partition(number): ... answer = set() ... answer.add((number, )) ... for x in range(1, number): ... for y in partition(number - x): ... answer.add(tuple(sorted((x, ) + y))) ... return answer ... >>> partition(4) set([(1, 3), (2, 2), (1, 1, 2), (1, 1, 1, 1), (4,)]) 如果你想所有的排列（即（1，3）和（3,1））改变answer.add(tuple(sorted((x, ) + y))到answer.add((x, ) + y)
比诺伦的function更小更快：
def partitions(n, I=1): yield (n,) for i in range(I, n//2 + 1): for p in partitions(ni, i): yield (i,) + p
我们来比较一下：
In [10]: %timeit -n 10 r0 = nolen(20) 1.37 s ± 28.7 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) In [11]: %timeit -n 10 r1 = list(partitions(20)) 979 µs ± 82.9 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) In [13]: sorted(map(sorted, r0)) == sorted(map(sorted, r1)) Out[14]: True
看起来它是n = 20的1370倍。
无论如何，它还远没有accel_asc ：
def accel_asc(n): a = [0 for i in range(n + 1)] k = 1 y = n - 1 while k != 0: x = a[k - 1] + 1 k -= 1 while 2 * x <= y: a[k] = x y -= x k += 1 l = k + 1 while x <= y: a[k] = x a[l] = y yield a[:k + 2] x += 1 y -= 1 a[k] = x + y y = x + y - 1 yield a[:k + 1]
它不仅更慢，而且需要更多的内存（但是显然更容易记住）：
In [18]: %timeit -n 5 r2 = list(accel_asc(50)) 114 ms ± 1.04 ms per loop (mean ± std. dev. of 7 runs, 5 loops each) In [19]: %timeit -n 5 r3 = list(partitions(50)) 527 ms ± 8.86 ms per loop (mean ± std. dev. of 7 runs, 5 loops each) In [24]: sorted(map(sorted, r2)) == sorted(map(sorted, r3)) Out[24]: True
您可以在ActiveState上find其他版本： 整数分区生成器（Python配方） 。
我使用Python 3.6.1和IPython 6.0.0。
我把这个解决scheme与perfplot （我的一个小项目）进行了比较，发现Nolen的顶级答案也是最慢的。
skovorodkin提供的答案都更快。
要生成剧情：
import perfplot import collections def nolen(number): answer = set() answer.add((number, )) for x in range(1, number): for y in nolen(number - x): answer.add(tuple(sorted((x, ) + y))) return answer def skovorodkin(n): return set(skovorodkin_yield(n)) def skovorodkin_yield(n, I=1): yield (n,) for i in range(I, n//2 + 1): for p in skovorodkin_yield(ni, i): yield (i,) + p def accel_asc(n): return set(accel_asc_yield(n)) def accel_asc_yield(n): a = [0 for i in range(n + 1)] k = 1 y = n - 1 while k != 0: x = a[k - 1] + 1 k -= 1 while 2 * x <= y: a[k] = x y -= x k += 1 l = k + 1 while x <= y: a[k] = x a[l] = y yield tuple(a[:k + 2]) x += 1 y -= 1 a[k] = x + y y = x + y - 1 yield tuple(a[:k + 1]) def mct(n): partitions_of = [] partitions_of.append([()]) partitions_of.append([(1,)]) for num in range(2, n+1): ptitions = set() for i in range(num): for partition in partitions_of[i]: ptitions.add(tuple(sorted((num - i, ) + partition))) partitions_of.append(list(ptitions)) return partitions_of[n] perfplot.show( setup=lambda n: n, kernels=[ nolen, mct, skovorodkin, accel_asc, ], n_range=range(1, 17), logy=True, # https://stackoverflow.com/a/7829388/353337 equality_check=lambda a, b: collections.Counter(set(a)) == collections.Counter(set(b)), xlabel='n' )
比接受的反应要快得多，而且看起来也不错。 接受的响应会多次执行大量相同的工作，因为它会多次计算较低整数的分区。 例如，当n = 22时，差值为12.7秒，相对于0.0467秒 。
def partitions_dp(n): partitions_of = [] partitions_of.append([()]) partitions_of.append([(1,)]) for num in range(2, n+1): ptitions = set() for i in range(num): for partition in partitions_of[i]: ptitions.add(tuple(sorted((num - i, ) + partition))) partitions_of.append(list(ptitions)) return partitions_of[n]
除了我们保存小整数的分区外，代码基本上是相同的，所以我们不必一次又一次地计算它们。
我不知道我的代码是否是最优雅的，但为了研究的目的，我不得不解决这个问题。 如果你修改
sub_nums
variables你可以限制分区中使用的数字。
def make_partitions(number): out = [] tmp = [] sub_nums = range(1,number+1) for num in sub_nums: if num<=number: tmp.append([num]) for elm in tmp: sum_elm = sum(elm) if sum_elm == number: out.append(elm) else: for num in sub_nums: if sum_elm + num <= number: L = [i for i in elm] L.append(num) tmp.append(L) return out
F(x,n) = \union_(i>=n) { {i}U g| g in F(xi,i) }
只要实现这个recursion。 F（x，n）是与x和它们的元素大于或等于n的所有集合的集合。
# -*- coding: utf-8 -*- import timeit ncache = 0 cache = {} def partition(number): global cache, ncache answer = {(number,), } if number in cache: ncache += 1 return cache[number] if number == 1: cache[number] = answer return answer for x in range(1, number): for y in partition(number - x): answer.add(tuple(sorted((x, ) + y))) cache[number] = answer return answer print('To 5:') for r in sorted(partition(5))[::-1]: print('\t' + ' + '.join(str(i) for i in r)) print( 'Time: {}\nCache used:{}'.format( timeit.timeit( "print('To 30: {} possibilities'.format(len(partition(30))))", setup="from __main__ import partition", number=1 ), ncache ) )
或https://gist.github.com/sxslex/dd15b13b28c40e695f1e227a200d1646
如果有人感兴趣：我需要解决一个类似的问题，即整数n分成非负部分，排列。 为此，有一个简单的recursion解决scheme（请参阅此处 ）：
def partition(n, d, depth=0): if d == depth: return [[]] return [ item + [i] for i in range(n+1) for item in partition(ni, d, depth=depth+1) ] # extend with n-sum(entries) n = 5 d = 3 lst = [[n-sum(p)] + p for p in partition(n, d-1)] print(lst)
输出：
[ [5, 0, 0], [4, 1, 0], [3, 2, 0], [2, 3, 0], [1, 4, 0], [0, 5, 0], [4, 0, 1], [3, 1, 1], [2, 2, 1], [1, 3, 1], [0, 4, 1], [3, 0, 2], [2, 1, 2], [1, 2, 2], [0, 3, 2], [2, 0, 3], [1, 1, 3], [0, 2, 3], [1, 0, 4], [0, 1, 4], [0, 0, 5] ]
