查找所有可能的子集总和给定的数

Question

我正在学习Python，我有一个问题，这似乎是一个简单的任务。

我想查找所有可能的总和给定数字的数字组合。
例如：4 - > [1,1,1,1] [1,1,2] [2,2] [1,3]

我挑选生成所有可能子集的解决方案（2^n），然后产生那些总和等于数量的那些。我的病情有问题。代码：

def allSum(number): 
    #mask = [0] * number 
    for i in xrange(2**number): 
     subSet = [] 
     for j in xrange(number): 
      #if : 
       subSet.append(j) 
     if sum(subSet) == number: 
      yield subSet 



for i in allSum(4): 
    print i 

顺便说一句，这是一个好方法？

Answer 1

下面是一些代码，我几年前看到的伎俩：

>>> def partitions(n): 
     if n: 
      for subpart in partitions(n-1): 
       yield [1] + subpart 
       if subpart and (len(subpart) < 2 or subpart[1] > subpart[0]): 
        yield [subpart[0] + 1] + subpart[1:] 
     else: 
      yield [] 

>>> print list(partitions(4)) 
[[1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]] 

其他参考：

• http://mathworld.wolfram.com/Partition.html
• http://en.wikipedia.org/wiki/Partition_(number_theory）
• http://www.site.uottawa.ca/~ivan/F49-int-part.pdf

Answer 2

该解决方案不起作用，对吧？它永远不会多次向一个子集添加一个数字，所以你永远不会得到，例如[1,1,2]。它永远不会跳过一个数字，所以你永远不会得到，例如，[1,3]。

所以你的解决方案的问题是双重的：一，你实际上并没有产生1..number范围内的所有可能的子集。二，所有子集的集合将排除你应该包括的东西，因为它不允许一个数字出现多次。

这种问题可以概括为搜索问题。想象一下，您想要尝试的数字是树上的节点，然后您可以使用深度优先搜索来查找树中代表解决方案的所有路径。这是一棵无限大的树，但幸运的是，你永远不需要搜索全部。

Answer 3

下面是其中的工作方式是采取全1的列表，并递归地通过添加后续元素折叠它的另一种方法，这应该不是生成所有可能的子集是更有效的：

def allSum(number): 
    def _collapse(lst): 
     yield lst 
     while len(lst) > 1: 
      lst = lst[:-2] + [lst[-2] + lst[-1]] 
      for prefix in _collapse(lst[:-1]): 
       if not prefix or prefix[-1] <= lst[-1]: 
        yield prefix + [lst[-1]] 
    return list(_collapse([1] * number)) 

>>> allSum(4) 
[[1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]] 
>>> allSum(5) 
[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], [1, 1, 3], [2, 3], [1, 4], [5]] 

可以剥去最后一个值，如果你不想要这个微不足道的情况。如果您只是循环播放结果，请删除list调用，然后返回发生器。

Answer 4

这相当于this question中描述的问题，可以使用类似的解决方案。

要阐述：

def allSum(number): 
    for solution in possibilites(range(1, number+1), number): 
     expanded = [] 
     for value, qty in zip(range(1, number+1), solution): 
      expanded.extend([value]*qty) 
     yield expanded 

这转化这个问题到了这个问题，然后再返回。