创建一个可能抽出的数字列表，使用列表中的数字‘访问’最多一个总和
创建一个可能抽出的数字列表，使用列表中的数字‘访问’最多一个总和
提问于 2016-01-05 04:07:29
我有一个数字列表，例如：
lst = [2,7]我想要所有可能的组合，可以访问到一个特定的数字n，例如
n=10因此，此列表将是：
[2,4,6,7,8,9,10]
(2 if 2 is drawn, 4 if 2 is drawn twice, 6 if 2 is drawn 3 times,
7 if 7 is drawn, 9 if 7 and 2 are drawn and 10 if 5 times 2 is drawn)我尝试了几种方法，但我一直发现这是一个非常困难的问题。有没有人知道是否有一种简单的方法可以做到这一点？
回答 3
Stack Overflow用户
发布于 2016-01-05 04:47:33
解决这个问题最简单的方法是使用递归。
下面是一些粗略的代码：
def find_possible_sums(numbers, possible, max, current):
for(number in numbers)
sum = current + number
if(sum <= max)
if(sum not in possible)
possible.append(sum)
find_possible_sums(numbers, possible, max, sum)其中numbers = lst，possible是所有可能的数字(开始为空)，max是n，sum是一个连续的总数(首先是0)。
如果您关心运行时，您可以对上面的解决方案进行许多进一步的优化。
Stack Overflow用户
发布于 2016-01-05 04:38:21
您正在寻找的是来自itertools：https://docs.python.org/2/library/itertools.html#itertools.combinations_with_replacement的combinations_with_replacement生成器
它将生成具有重复的k个元素的所有组合。你必须为k的每个可能的值调用它-在你的例子中是从1到n(包括1到n)。在此之后，您必须对每个组合中的值求和。
示例：
from itertools import combinations_with_replacement, imap, islice
lst = [2,7]
n = 10
combinations = (combinations_with_replacement(lst, k) for k in xrange(1, n + 1))
all_combinations = chain(combinations)
first_5 = islice(imap(sum, all_combinations), 0, 5) # Grap the first five.我使用生成器，因为可能的组合列表增长得相当快。
Stack Overflow用户
发布于 2016-01-05 05:40:09
Python 3的非递归解决方案：
from itertools import chain, takewhile, combinations_with_replacement, count
lst = [2, 7]
l = sorted(lst)
n = 10
set(
chain.from_iterable(
takewhile(
lambda x: x != (),
map(tuple,
(takewhile(
lambda x: x <= n,
map(
lambda x: sum(x),
combinations_with_replacement(l, p))
) for p in count(1)
)
)
)
)
){2，4，6，7，8，9，10}
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/34598973
复制相关文章
相似问题
腾讯云开发者
