整数分区的优雅 Python 代码[关闭]
- 2024-12-31 08:37:00
- admin 原创
- 110
问题描述：
我尝试编写代码来解决标准整数分区问题（Wikipedia）。我编写的代码很乱。我需要一个优雅的解决方案来解决这个问题，因为我想改进我的编码风格。这不是家庭作业问题。
解决方案 1：
比 Nolen 函数更小更快：
def partitions(n, I=1):
yield (n,)
for i in range(I, n//2 + 1):
for p in partitions(n-i, 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
看起来它的速度快了 1370 倍n = 20。
无论如何，它仍然远远不够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：整数分区生成器（Python 配方）上找到其他版本。
我使用 Python 3.6.1 和 IPython 6.0.0。
解决方案 2：
虽然这个答案很好，但我还是推荐 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)
解决方案 3：
我将该解决方案与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(n - i, 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",
)
解决方案 4：
我需要解决一个类似的问题，即将整数分成n非d负部分，并进行排列。为此，有一个简单的递归解决方案（参见此处）：
def partition(n, d, depth=0):
if d == depth:
return [[]]
return [
item + [i]
for i in range(n+1)
for item in partition(n-i, 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]
]
解决方案 5：
比接受的响应快得多，而且看起来也不错。接受的响应多次执行大量相同的工作，因为它多次计算较低整数的分区。例如，当 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]
代码本质上是相同的，只是我们保存了较小整数的分区，所以我们不必一次又一次地计算它们。
解决方案 6：
我参与这个游戏有点晚了，但我可以提供一个在某种意义上可能更优雅的贡献：
def partitions(n, m = None):
"""Partition n with a maximum part size of m. Yield non-increasing
lists in decreasing lexicographic order. The default for m is
effectively n, so the second argument is not needed to create the
generator unless you do want to limit part sizes.
"""
if m is None or m >= n: yield [n]
for f in range(n-1 if (m is None or m >= n) else m, 0, -1):
for p in partitions(n-f, f): yield [f] + p
仅需 3 行代码。按字典顺序输出。可选择允许设置最大部件大小。
对于具有给定数量部分的分区，我对上述内容也进行了变体：
def sized_partitions(n, k, m = None):
"""Partition n into k parts with a max part of m.
Yield non-increasing lists. m not needed to create generator.
"""
if k == 1:
yield [n]
return
for f in range(n-k+1 if (m is None or m > n-k+1) else m, (n-1)//k, -1):
for p in sized_partitions(n-f, k-1, f): yield [f] + p
在编写完上述内容后，我偶然发现了一个我近 5 年前创建的解决方案，但我已将其忘记。除了最大零件尺寸外，该解决方案还提供了附加功能，您可以强制设置最大长度（而不是特定长度）。FWIW：
def partitions(sum, max_val=100000, max_len=100000):
""" generator of partitions of sum with limits on values and length """
# Yields lists in decreasing lexicographical order.
# To get any length, omit 3rd arg.
# To get all partitions, omit 2nd and 3rd args.
if sum <= max_val: # Can start with a singleton.
yield [sum]
# Must have first*max_len >= sum; i.e. first >= sum/max_len.
for first in range(min(sum-1, max_val), max(0, (sum-1)//max_len), -1):
for p in partitions(sum-first, first, max_len-1):
yield [first]+p
解决方案 7：
这是一个递归函数，它使用堆栈，我们在堆栈中按升序存储分区的编号。它足够快并且非常直观。
# get the partitions of an integer
Stack = []
def Partitions(remainder, start_number = 1):
if remainder == 0:
print(" + ".join(Stack))
else:
for nb_to_add in range(start_number, remainder+1):
Stack.append(str(nb_to_add))
Partitions(remainder - nb_to_add, nb_to_add)
Stack.pop()
当堆栈已满时（堆栈元素的总和对应于我们想要的分区数），我们打印它，删除其最后一个值并测试下一个可能存储在堆栈中的值。当所有下一个值都已测试后，我们再次弹出堆栈的最后一个值并返回到最后一个调用函数。以下是输出示例（8）：
Partitions(8)
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1 + 2
1 + 1 + 1 + 1 + 1 + 3
1 + 1 + 1 + 1 + 2 + 2
1 + 1 + 1 + 1 + 4
1 + 1 + 1 + 2 + 3
1 + 1 + 1 + 5
1 + 1 + 2 + 2 + 2
1 + 1 + 2 + 4
1 + 1 + 3 + 3
1 + 1 + 6
1 + 2 + 2 + 3
1 + 2 + 5
1 + 3 + 4
1 + 7
2 + 2 + 2 + 2
2 + 2 + 4
2 + 3 + 3
2 + 6
3 + 5
4 + 4
8
递归函数的结构很容易理解，如下所示（针对整数 31）：
%7D%7D%7B%5Coverbrace%7B1,1,3,5,%5Cunderset%7B%5Ctext%7Bgiven&space;by&space;Partitions(21,5)%7D%7D%7B%5Cunderbrace%7B5,7,9%7D%7D%7D%7D]$$ "$$Pile=[overset{ ext{由 Partitions(31,1) 给出}}{overbrace{1,1,3,5,/underset{ ext{由 Partitions(21,5) 给出}}{/underbrace{5,7,9}}}}]$$")
remainder对应于我们想要分区的剩余数字的值（上例中为 31 和 21）。start_number对应于分区的第一个数字，其默认值为 1（上例中为 1 和 5）。
如果我们想要以列表形式返回结果并获取分区的数量，我们可以这样做：
def Partitions2_main(nb):
global counter, PartitionList, Stack
counter, PartitionList, Stack = 0, [], []
Partitions2(nb)
return PartitionList, counter
def Partitions2(remainder, start_number = 1):
global counter, PartitionList, Stack
if remainder == 0:
PartitionList.append(list(Stack))
counter += 1
else:
for nb_to_add in range(start_number, remainder+1):
Stack.append(nb_to_add)
Partitions2(remainder - nb_to_add, nb_to_add)
Stack.pop()
最后，上面显示的函数的一个很大的优点Partitions是它可以很容易地适应找到自然数的所有组合（两个组合可以具有相同的数字集，但在这种情况下顺序不同）：我们只需要删除变量start_number并在循环中将其设置为 1 for。
# get the compositions of an integer
Stack = []
def Compositions(remainder):
if remainder == 0:
print(" + ".join(Stack))
else:
for nb_to_add in range(1, remainder+1):
Stack.append(str(nb_to_add))
Compositions(remainder - nb_to_add)
Stack.pop()
输出示例：
Compositions(4)
1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
1 + 3
2 + 1 + 1
2 + 2
3 + 1
4
解决方案 8：
我认为这里的菜谱可以算得上是优雅的。它简洁（20 行），速度快，并且基于 Kelleher 和 O'Sullivan 的作品，其中引用了这些作品：
def aP(n):
"""Generate partitions of n as ordered lists in ascending
lexicographical order.
This highly efficient routine is based on the delightful
work of Kelleher and O'Sullivan.
Examples
========
>>> for i in aP(6): i
...
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 2]
[1, 1, 1, 3]
[1, 1, 2, 2]
[1, 1, 4]
[1, 2, 3]
[1, 5]
[2, 2, 2]
[2, 4]
[3, 3]
[6]
>>> for i in aP(0): i
...
[]
References
==========
.. [1] Generating Integer Partitions, [online],
Available: http://jeromekelleher.net/generating-integer-partitions.html
.. [2] Jerome Kelleher and Barry O'Sullivan, "Generating All
Partitions: A Comparison Of Two Encodings", [online],
Available: http://arxiv.org/pdf/0909.2331v2.pdf
"""
# The list `a`'s leading elements contain the partition in which
# y is the biggest element and x is either the same as y or the
# 2nd largest element; v and w are adjacent element indices
# to which x and y are being assigned, respectively.
a = [1]*n
y = -1
v = n
while v > 0:
v -= 1
x = a[v] + 1
while y >= 2 * x:
a[v] = x
y -= x
v += 1
w = v + 1
while x <= y:
a[v] = x
a[w] = y
yield a[:w + 1]
x += 1
y -= 1
a[v] = x + y
y = a[v] - 1
yield a[:w]
解决方案 9：
# -*- 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(' ' + ' + '.join(str(i) for i in r))
print(
'Time: {}
Cache 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
解决方案 10：
我不知道我的代码是否最优雅，但出于研究目的，我不得不多次解决这个问题。如果你修改
sub_nums
变量您可以限制分区中使用的数字。
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
解决方案 11：
F(x,n) = /union_(i>=n) { {i}U g| g in F(x-i,i) }
只需实现这个递归。F(x,n) 是所有和为 x 且其元素大于或等于 n 的集合的集合。
相关推荐
热门文章
项目管理软件有哪些？
热门标签
云禅道AD
