我正在尝试找到一种方法，以显示所有可能的X个整数集合，这些集合加起来等于给定的整数。例如，要获取使5的所有2个整数集合，我将有：
1, 4
2, 3
或者对于使得6的三个整数:
1, 1, 4
1, 2, 3
2, 2, 2
我只需要整数，不包括0，并且它只需要在一组最大为15、最大数字为30的情况下工作。
我甚至不确定这在数学上是否有一个术语。我猜类似于因数分解？
获取所有加起来等于一个数字的数字
24
- Sam Machin
3
http://zh.wikipedia.org/wiki/%E5%88%86%E7%B5%84_(%E6%95%B8%E8%AB%96)
http://mathworld.wolfram.com/Partition.html
http://code.activestate.com/recipes/218332/ - e.tadeu
1最不含糊/最准确的说法应该是“正整数”，而不是“整数”、“数字”或“整数”。 - Devin Jeanpierre
+1。很好的问题。在数论中，G.H.哈代和S.拉马努金已经研究了大量相关理论。 - Guru
5个回答
21
这里有一种解决问题的方法：
def sum_to_n(n, size, limit=None):
"""Produce all lists of `size` positive integers in decreasing order
that add up to `n`."""
if size == 1:
yield [n]
return
if limit is None:
limit = n
start = (n + size - 1) // size
stop = min(limit, n - size + 1) + 1
for i in range(start, stop):
for tail in sum_to_n(n - i, size - 1, i):
yield [i] + tail
for partition in sum_to_n(6, 3):
print partition
[2, 2, 2]
[3, 2, 1]
[4, 1, 1]
- Jason Orendorff
11
这里有一个代码片段（链接）：
from itertools import combinations, chain
def sum_to_n(n):
'Generate the series of +ve integer lists which sum to a +ve integer, n.'
from operator import sub
b, mid, e = [0], list(range(1, n)), [n]
splits = (d for i in range(n) for d in combinations(mid, i))
return (list(map(sub, chain(s, e), chain(b, s))) for s in splits)
使用方法如下：
for p in sum_to_n(4):
print p
输出：
[4] [1, 3] [2, 2] [3, 1] [1, 1, 2] [1, 2, 1] [2, 1, 1] [1, 1, 1, 1]
- jbochi
3
2这个的时间和空间复杂度是多少？ - Hamish Grubijan
2通常情况下，[1,3]和[3,1]被认为是相同的分区。 - Stephen Canon
应该使用一组frozensets来跟踪分区，然后再返回它们。您可以将sum_to_n转换为生成器函数，以使检查包含更方便和可读。 - Devin Jeanpierre
2
这些被称为该整数的划分，其他人已经提供了定义链接。
通常可以通过递归来完成这些操作。例如，假设我想以恰好三个整数的和的形式构建10的所有不同方式，且三个整数没有重复。
查看该总和中最大的可能组件。它可能是10吗？不可能，因为如果最大组件为10，则剩下什么？即10-10=0。事实证明，如果总和中的最大元素为7，则剩下要划分为两个正整数的元素为3。我们可以将3分解为两个不同整数的总和，刚好有一种方式。所以{7,2,1}就是这样一个划分，也是唯一涉及到7这么大元素的划分。
6能用作最大元素吗？如果可以，那么我们将剩下4。我们可以以一种方式将4分解为{6,3,1}。进一步搜索将产生10的其他分区，如{5,4,1}，{5,3,2}。没有其他可能存在。
关键是，可以轻松地将此操作定义为递归函数。通过仔细编码，甚至可以使用记忆化技术，以避免重新计算以前看过的内容。
- user85109
0
感谢 @Jason Orendorff - 我进一步开发了您的函数，因为我需要更多选项。
现在可以指定最小和最大加数计数，并对组合进行排列。
请注意 max_summand_count: 如果设置得太高，会陷入递归地狱 :)
from itertools import permutations
def get_all_possible_summands_to_n(n, min_summand_count=1, max_summand_count=5, min_summand=1, max_summand=None, permutate=False):
if min_summand_count < 1:
raise ValueError("min_summand_count may not be below 1")
if min_summand < 1:
raise ValueError("min_summand may not be below 1")
if not max_summand_count:
max_summand_count = n
if max_summand is None:
max_summand = n
for size in range(min_summand_count, max_summand_count + 1):
if size == 1 and n <= max_summand:
yield [n]
continue
start = (n + size - 1) // size
stop = min(max_summand, n - size + 1) + 1
for i in range(start, stop):
if (size-1) > 0:
for tail in get_all_possible_summands_to_n(n - i, size - 1, size - 1, min_summand, i):
result = list([i] + list(tail))
if [c for c in result if c >=min_summand] == result:
if permutate:
for combination in list(set(permutations(result, len(result)))):
yield list(combination)
else:
yield result
这里是它通过的所有测试：
def test_get_all_possible_summands_to_n(self):
# BASICS
self.assertEqual(
list(get_all_possible_summands_to_n(3)),
[[3], [2,1], [1,1,1]]
)
# permutation
self.assertEqual(
list(get_all_possible_summands_to_n(3, permutate=True)),
[[3], [1,2], [2,1], [1,1,1]]
)
# MIN / MAX SUMMAND
self.assertEqual(
list(get_all_possible_summands_to_n(4)),
[[4], [2, 2], [3, 1], [2, 1, 1], [1, 1, 1, 1]]
)
# min summand
self.assertEqual(
list(get_all_possible_summands_to_n(4, min_summand=2)),
[[4], [2, 2]]
)
self.assertEqual(
list(get_all_possible_summands_to_n(4, min_summand=3)),
[[4]]
)
# max summand
self.assertEqual(
list(get_all_possible_summands_to_n(4, max_summand=2)),
[[2, 2], [2, 1, 1], [1, 1, 1, 1]]
)
self.assertEqual(
list(get_all_possible_summands_to_n(4, max_summand=3)),
[[2, 2], [3, 1], [2, 1, 1], [1, 1, 1, 1]]
)
# min / max summand combination
self.assertEqual(
list(get_all_possible_summands_to_n(5)),
[[5], [3, 2], [4, 1], [2, 2, 1], [3, 1, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]
)
self.assertEqual(
list(get_all_possible_summands_to_n(5, min_summand=2, max_summand=3)),
[[3, 2]]
)
self.assertEqual(
list(get_all_possible_summands_to_n(6, min_summand=3, max_summand=3)),
[[3, 3]]
)
# MIN / MAX SUMMAND COUND
self.assertEqual(
list(get_all_possible_summands_to_n(6)),
[
[6],
[3, 3],
[4, 2],
[5, 1],
[2, 2, 2],
[3, 2, 1],
[4, 1, 1],
[2, 2, 1, 1],
[3, 1, 1, 1],
[2, 1, 1, 1, 1]
]
)
# min summand count
self.assertEqual(
list(get_all_possible_summands_to_n(6, min_summand_count=3)),
[
[2, 2, 2],
[3, 2, 1],
[4, 1, 1],
[2, 2, 1, 1],
[3, 1, 1, 1],
[2, 1, 1, 1, 1]
]
)
# max summand count
self.assertEqual(
list(get_all_possible_summands_to_n(6, max_summand_count=3)),
[
[6],
[3, 3],
[4, 2],
[5, 1],
[2, 2, 2],
[3, 2, 1],
[4, 1, 1],
]
)
# min max summand count combination
self.assertEqual(
list(get_all_possible_summands_to_n(6, min_summand_count=2, max_summand_count=3)),
[
[3, 3],
[4, 2],
[5, 1],
[2, 2, 2],
[3, 2, 1],
[4, 1, 1],
]
)
self.assertEqual(
list(get_all_possible_summands_to_n(6, min_summand_count=3, max_summand_count=3)),
[
[2, 2, 2],
[3, 2, 1],
[4, 1, 1],
]
)
# ALL COMBINATIONS
self.assertEqual(
list(get_all_possible_summands_to_n(12, min_summand_count=2, max_summand_count=3, min_summand=2, max_summand=3)),
[]
)
self.assertEqual(
list(
get_all_possible_summands_to_n(
12,
min_summand_count=4,
max_summand_count=5,
min_summand=2,
max_summand=4
)
),
[
[3, 3, 3, 3],
[4, 3, 3, 2],
[4, 4, 2, 2],
[3, 3, 2, 2, 2],
[4, 2, 2, 2, 2]
]
)
随意优化其性能和优雅：） - 我相信有潜力这样做。
- user1383029
0
你的问题可以这样重新表述：
给定一个数字N，找到所有满足每个集合之和等于N的集合[S1，S2，S3 ......]。集合的大小由数字L给出。
首先让我们考虑 L=2 的情况。这意味着您可以拥有以下集合：
(9,1) , (8,2), (7,3) , (6,4) , (5,5)
我将其称为基本解决方案，很快您就会明白原因。
现在让我们将 L 更改为 3 并重新回答：
所以让我们考虑数字 9。是否存在这样的列表 L，使得 sum(L) + 9 = 10？显然答案是否定的，但有趣的是问题本身。我们基本上正在寻找一组可以相加成数字 1 的 2 个元素的集合。这与基本解决方案解决的问题相同。
因此，对于 [9,8,7,6,5,4,3,2,1] 中的每个数字 x，您都要尝试找到一个集合 [a,b]，使得 x+a+b = 10。
这不是一个完整的答案，但是思路是你要看到这里的模式，并使用递归来计算基本情况，就像上面所做的那样，然后找出递归调用来完成你的解决方案。祝你好运！
- Arnab Datta
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接