使用递归计算长度为n的列表中的长度k的组合

Question

我需要k从长度列表中生成长度的所有组合n,我必须使用递归来完成.

例如:

INPUT:  choose_sets([1,2,3,4],3)
OUTPUT: [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

INPUT:  choose_sets([1,2,3,4],2)
OUTPUT: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

我在代码中执行此操作时遇到困难,所以我很乐意提供一些帮助.到目前为止这是我的代码(我遗漏的东西只是不知道是什么):

def choose_sets(lst,k):

    if k == len(lst):
        return lst
    if k == 0:
        return []
    if k > len(lst):
        return []

    sets=[]
    sub_lst=lst[:]
    sub_lst.remove(sub_lst[0])

    a= choose_sets(sub_lst,k-1)
    for i in a:
        i.append(lst[0])
    sets.append(a)

    b= choose_sets(sub_lst,k)
    sets.append(b)


    return sets

Answer 1

您可以从Generator获取解决方案的排列,组合和选择(Python配方)

def xuniqueCombinations(items, n):
    if n==0: yield []
    else:
        for i in xrange(len(items)):
            for cc in xuniqueCombinations(items[i+1:],n-1):
                yield [items[i]]+cc



>>> def xuniqueCombinations(items, n):
...     if n==0: yield []
...     else:
...         for i in xrange(len(items)):
...             for cc in xuniqueCombinations(items[i+1:],n-1):
...                 yield [items[i]]+cc
... 
>>> for x in xuniqueCombinations( [1,2,3,4],2):
...     print x
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]

4年后编辑 (2015 年12月7日)

要在Python3上运行它只需更改xrange为range,Python3的范围是Python2的xrange..谢谢@ederollora注意到我.