python 获取所有与数字相加的数字
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2065553/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Get all numbers that add up to a number
提问by Sam Machin
I'm trying to find a way to display all the possible sets of X integers that add up to a given integer. for example to get all 2 integer sets that make 5 I would have:
我试图找到一种方法来显示加起来等于给定整数的所有可能的 X 整数集。例如，要获得使 5 的所有 2 个整数集，我将拥有：
1, 4
2, 3
Or for 3 integers that make 6:
或者对于 6 的 3 个整数：
1, 1, 4
1, 2, 3
2, 2, 2
I only need whole numbers not including 0 and it only needs to work on up to about 15 in a set and 30 max. number.
我只需要不包括 0 的整数，并且它只需要在一组中最多处理大约 15 个和最多 30 个。数字。
I'm not even sure if this has a term mathematically. It's similar to factorisation I guess?
我什至不确定这是否有数学术语。它类似于我猜的因式分解？
采纳答案by Jason Orendorff
Here is one way to solve this problem:
这是解决此问题的一种方法：
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
You can use it like this.
你可以像这样使用它。
for partition in sum_to_n(6, 3):
print partition
[2, 2, 2]
[3, 2, 1]
[4, 1, 1]
回答by jbochi
There's a snippet here:
有一个片段在这里：
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)
Use it like this:
像这样使用它：
for p in sum_to_n(4):
print p
Outputs:
输出：
[4] [1, 3] [2, 2] [3, 1] [1, 1, 2] [1, 2, 1] [2, 1, 1] [1, 1, 1, 1]
回答by jbochi
These are called partitions of the integer in question. Others have provided links to define them.
这些被称为所讨论的整数的分区。其他人提供了定义它们的链接。
A trick to do these things is often to do them recursively. For example, suppose I wanted to form all distinct ways to build 10 as the sum of exactly three integers, none of which appears more than once.
做这些事情的一个技巧通常是递归地做它们。例如，假设我想形成所有不同的方法来构建 10 作为正好三个整数的总和，其中没有一个出现超过一次。
Look at the largest possible component in that sum. Can it be 10? No, since if the largest component is a 10, then what remains? I.e., 10 - 10 = 0. It turns out that if the largest element in the sum is a 7, then what remains, to be partitioned into a sum of two positive integers is 3. And we can break 3 into a sum of two distinct integers in exactly one way. So {7,2,1} is such a partition, and the only partition that involves an element as large as 7.
查看该总和中可能的最大分量。可以是10吗？不，因为如果最大的分量是 10，那么还剩下什么？即，10 - 10 = 0。事实证明，如果总和中的最大元素是 7，那么剩下的要划分为两个正整数之和的是 3。我们可以将 3 分解为两个之和完全不同的整数以一种方式。所以{7,2,1}就是这样一个分区，也是唯一一个涉及到7这样大的元素的分区。
Can 6 be used as the largest element? If so, then we would have 4 remaining. And we can break 4 in exactly one way, to yield the partition {6,3,1}. Further searching will yield other partitions of 10 as {5,4,1}, {5,3,2}. No others can exist.
6 可以用作最大的元素吗？如果是这样，那么我们将剩下 4 个。我们可以以一种方式打破 4，得到分区 {6,3,1}。进一步搜索将产生其他 10 分区，如 {5,4,1}、{5,3,2}。没有其他人可以存在。
The point is, this operation can easily be defined as a recursive function. With careful coding, one might even use memoization, to avoid recomputing that which we have seen before.
关键是，这个操作可以很容易地定义为一个递归函数。通过仔细编码，人们甚至可以使用记忆化，以避免重新计算我们之前看到的内容。
回答by Arnab Datta
Your question can be rephrased like this :
你的问题可以这样改写：
Given a number N, find all sets [S1, S2, S3 .....] where the sum of each set equals N. The size of the sets are given by the number L.
给定一个数字 N，找出所有集合 [S1, S2, S3 .....] 其中每个集合的总和等于 N。集合的大小由数字 L 给出。
First let's consider the case of L=2.This means that you can have the following sets
首先让我们考虑 的情况。L=2这意味着您可以拥有以下集合
(9,1) , (8,2), (7,3) , (6,4) , (5,5)
(9,1) , (8,2), (7,3) , (6,4) , (5,5)
I'll call this the base solution and you'll soon see why.
我将其称为基本解决方案，您很快就会明白为什么。
Let's change our L to 3 now and redo our answer :
现在让我们将 L 更改为 3 并重做我们的答案：
So let's consider the number 9. Does there exist such a list Lsuch that sum(L) + 9 = 10? The obvious answer is No, but what's interesting here is not the answer but the question itself. We are basically asking for a set of 2elements that can be summed up to be the number 1. This is the same problem that was solved by the base solution.
因此，让我们考虑数9.确实存在这样的列表L，以便sum(L) + 9 = 10？显而易见的答案是否定的，但这里有趣的不是答案而是问题本身。我们基本上要求一组2可以总结为数字的元素1。这与基本解决方案解决的问题相同。
So therefore for each number xin [9,8,7,6,5,4,3,2,1]you try to find a set [a,b]such that x+a+b = 10.
因此，对于您中的每个数字x，[9,8,7,6,5,4,3,2,1]尝试找到一个集合[a,b]，使得x+a+b = 10.
This isn't a complete answer, but the idea is that you see the pattern here, and use recursion to calculate the base case as done above and then figure out the recursive call that will complete your solution. Good luck!
这不是一个完整的答案，但我们的想法是您看到这里的模式，并使用递归来计算上述基本情况，然后找出将完成您的解决方案的递归调用。祝你好运！
