使用lis中的数字创建一个可能绘制的数字列表，以“访问”到一个总和

Question

我有一个数字列表，例如：

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)

我试过好几种方法，但我一直觉得这是一个非常困难的问题。有没有人知道有没有一个简单的方法可以做到这一点？你知道吗

Answer 1

您要寻找的是itertools中的带有替换生成器的组合：https://docs.python.org/2/library/itertools.html#itertools.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.

我使用生成器是因为可能的组合列表增长非常快。你知道吗

Answer 2

解决这个问题最简单的方法是使用递归。你知道吗

下面是一些粗略的代码：

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）。你知道吗

如果您关心运行时，可以对上述解决方案进行许多进一步的优化。你知道吗

Answer 3

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}