查找所有可能的子集總和給定的數

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 

這轉化這個問題到了這個問題，然後再返回。