用于整数分区的优雅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] ]