在Python中递归地生成n个choose k组合的列表，但返回一个lis

Question

我试图通过对每个递归调用遵循include或notinclude一个元素的策略递归地生成一个列表的所有n个choose k组合（不检查唯一性）。我当然可以打印出组合，但我一辈子都不知道如何用Python返回正确的列表。下面是一些尝试：

class getCombinationsClass:

    def __init__(self,array,k):

        #initialize empty array
        self.new_array = []
        for i in xrange(k):
            self.new_array.append(0)

        self.final = []

        self.combinationUtil(array,0,self.new_array,0,k)

    def combinationUtil(self,array,array_index,current_combo, current_combo_index,k):

        if current_combo_index == k:
            self.final.append(current_combo)
            return

        if array_index >= len(array):
            return

        current_combo[current_combo_index] = array[array_index]

        #if current item included
        self.combinationUtil(array,array_index+1,current_combo,current_combo_index+1,k)

        #if current item not included
        self.combinationUtil(array,array_index+1,current_combo,current_combo_index,k)

在上面的例子中，我试图将结果附加到一个似乎不起作用的外部列表中。我还尝试通过递归构造一个最终返回的列表来实现这一点：

^{pr2}$

当我对list[1,2,3]和k=2进行测试时，对于这两个实现，我一直得到结果[[3,3]，[3,3]，[3,3]]。但是，如果我实际上在内部（current_combo_index==k）if语句中打印出“current_combo”变量，则会打印出正确的组合。什么给予？我误解了与变量范围或Python列表有关的东西？在

Answer 1

看看这个：itertools.combinations。您也可以看看实现。在

Answer 2

第二种方法出错是因为

return [current_combo]

返回对当前“组合”的引用。在程序结束时，返回的所有组合都是对同一当前组合的引用。在

您可以通过将该行更改为以下内容来复制当前的\u组合框来解决此问题：

^{pr2}$

第一种方法失败的原因相同，您需要更改：

self.final.append(current_combo)

到

self.final.append(current_combo[:])