递归生成 n 的列表，在 Python 中选择 k 组合 - 但是 return 列表

Question

我试图通过遵循为每个递归调用包含或不包含元素的策略递归地生成列表的所有 n 选择 k 组合（不检查唯一性）。我绝对可以打印出这些组合，但我终究无法弄清楚如何 return 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)

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

def getCombinations(array,k):

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

    return getCombinationsUtil(array,0,new_array,0,k)

def getCombinationsUtil(array,array_index,current_combo, current_combo_index,k):

    if current_combo_index == k:
        return [current_combo]

    if array_index >= len(array):
        return []

    current_combo[current_combo_index] = array[array_index]

    #if current item included & not included
    return getCombinationsUtil(array,array_index+1,current_combo,current_combo_index+1,k) + getCombinationsUtil(array,array_index+1,current_combo,current_combo_index,k)

当我对列表 [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]

returns 对 current_combo 的引用。在程序结束时，返回的所有组合都是对相同 current_combo.

的引用

您可以通过将 current_combo 行更改为以下内容来制作 current_combo 的副本来解决此问题：

return [current_combo[:]]

第一种方法同样失败，需要修改：

self.final.append(current_combo)

到

self.final.append(current_combo[:])

递归生成 n 的列表，在 Python 中选择 k 组合 - 但是 return 列表

Recursively Generating a List of n choose k combinations in Python - BUT return a list

python

algorithm

recursion

combinations

list