使用递归计算长度为k的组合，给定一个长度为n的列表。

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

- user1123417

---

我正在使用Python，但输出结果并不正确，我真的不知道该如何使其正确。 - user1123417

是的，保罗，我已经尝试了几个小时，但还是做不对。 - user1123417

你是否可以使用迭代？最明显的算法将遍历整个集合，但在每次迭代时它会递归地对较小的集合调用自身。(这大概是我能给出的提示了，否则就会暴露答案)。 - Adrian Ratnapala

嗨，Adrian，是的，只要我在迭代中有递归调用就可以使用它。你能详细说明一下解决方案吗？我知道它需要在一个较小的集合上调用自身，但我无法正确实现它... - user1123417

Stack Overflow不提供调试服务 - 如果问题特别涉及代码尝试，则需要明确定义的问题，明确针对该问题提出的问题以及从整体算法中隔离出有问题的部分的[mre]。更自然的解释是问题仅涉及任务；必须以特定方式编写代码（例如“使用递归”）并不会使其成为不同的问题。我将其关闭为重复项；规范文档已经使用递归回答了这个问题，幸运的是。 - Karl Knechtel

Answer 1

您可以从生成器中获取序列的排列、组合、选择解决方案（Python recipe）。

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]

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

如果要在Python3上运行，请将xrange更改为range，Python3的range就是Python2的xrange。感谢@ederollora提醒我。

- dani herrera

---

当我尝试repl one时，出现了“类型为'int'的对象没有len()”的错误。 - Christofer Ohlsson

@ChristoferOhlsson，请确保第一个参数是可枚举的。 - dani herrera

谢谢，这救了我的命！ - Blairg23

这适用于Python27，不适用于Python35，可能是因为xrange不能使用。只需将其更改为range。已检查在Python35中工作。 - ederollora

@ederollora，是的，只需将xrange更改为range，Python3的range就是Python2的xrange。 - dani herrera

Answer 2

看一下这个解决方案：

def choose_sets(mylist,length):
    mylen = len(mylist)

    if length == mylen:
        return [mylist]
    if length == 1:
        return [[i] for i in mylist]
    if length > mylen:
        return []

    ToRet = []
    for k in xrange(mylen): 
        if mylen - k + 1> length :
            for j in choose_sets(mylist[k+1:],length-1):
                New = [mylist[k]]
                New.extend(j)
                ToRet.append(New)
    return ToRet

print choose_sets([1,2,3,4,5],3)

有更优雅的方法，但这应该作为家庭作业是可以的...

- jimifiki

Answer 3

这是Java编写的，我不能保证它能够100%正常工作，但基于快速原型制作，似乎可以正常工作。无论如何，希望这对你有所帮助。

public void choose_sets(int values[], int count) {
    int perm[] = new int[count];
    choose_sets(values, 0, perm, 0, count);
}

public void choose_sets(int[] values, int valuesIdx, int[] perm,
                        int permIdx, int count) {
    if (permIdx == count) {
        // At this point perm -array contains single permutation
        // of length ´count´.
    } else {
        for (int i = valuesIdx; i < values.length; ++i) {
            perm[permIdx] = values[i];
            choose_sets(values, i + 1, perm, permIdx + 1, count);
        }
    }
}

- harism

Answer 4

你已经接近成功了，只需要做一些小的调整。算法基本上是正确的，但是

if k == len(lst):
    return lst

这个类型不正确。返回类型不是一个thing列表，而是一个（thing列表）的列表，所以应该是

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

接下来，

if k == 0:
    return []

每个列表都有一个非空子列表，即空列表，因此应该是：

if k == 0:
    return [[]]

对于其余的部分，

if k > len(lst):
    return []

是完全正确的。

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

这是正确的，但可以更简洁地表达为

sub_lst = lst[1:]

现在，又是另一种类型混淆：

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

sets.append(a) 将 a 放入 sets 的一个插槽中，如果你想要连接这两个列表，可以使用 sets = sets + a。如果你希望组合的顺序与列表中元素出现的顺序相同，而不是使用 i.append(lst[0])，则应该在循环中将 [lst[0]] + i 添加到 sets 中，但这只是一种偏好问题。

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

再次强调，在这里不要追加，而是要连接起来，

sets = sets + b

- Daniel Fischer

---

如果你使用的是 for i in a: i.append(lst[0])，那么我不知道为什么会出错，因为这个在这里是正确的。如果你使用的是 for i in a: i = [lst[0]] + i，那是因为我总是忘记 Python 的作用域规则。最初我使用的是 for i in a: sets.append([lst[0]]+i)，这个也能工作，但是在循环中对i进行赋值并不能改变a 中的元素。 - Daniel Fischer

Answer 5

基本上你需要使用以下递归：

f(k,n) = append_to_each( f(k-1,n-1), n) | f(k,n-1)

def combinations(lst,k):
    n = len(lst)
    if n == k:
        return [set(lst)]
    if k == 1:
        return [set([lst[i]]) for i in range(n)]
    v1 = combinations(lst[:-1], k-1)
    v1new = [ i.add(lst[n-1]) for i in v1]
    v2 = combinations(lst[:-1], k)
    return v1+v2

- ElKamina