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

Question

我需要从长度为n的列表中生成长度为k的所有组合，并且我必须使用递归来完成。

例如：

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

给看看这个解决方案：

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) 

有更优雅的方式，但这种应该没问题作为作业...

Answer 2

这是在Java中，我不能保证它正常工作，但基于快速原型开发似乎工作正常。希望这在一定程度上有所帮助。

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); 
     } 
    } 
} 

Answer 3

你可以从Generator for permutations, combinations, selections of a sequence (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] 

解决方案编写了4个一年后（2015年7月12日）

要在Python3运行它只是改变xrange到range， Python3's range is Python2's xrange.。感谢@ederollora来通知我。

Answer 4

你几乎在那里，只是一些小事情。算法基本正确，但是

if k == len(lst): 
    return lst 

这有错误的类型。返回类型不是事情清单，但（的事情列表）的列表，所以这应该是

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 

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