Computing combinations of length k from a list of length n using recursion

Question

I need to generate all combinations of length k from a list of length n , and I have to do this with recursion.

Example:

 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]] 

I am stuck in implementing this code, so I would be happy for the help. This is my code so far (I will miss something, I just don’t know what):

 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

You can get a solution from Generator for permutations, combinations, sequence selection (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] 

Edited 4 years later (12/12/2015)

To run it in Python3, just change xrange to range , the range of Python3 is Python2 xrange. . Thanks @ederollora for noticing me.

Answer 2

This is in Java, and I can’t guarantee that it works 100% correctly, but based on rapid prototyping, it seems to work fine. Hope this helps anyway.

 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

Take a look at this solution:

 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) 

There are more elegant ways, but it should be fine, like homework ...

Answer 4

You're almost there, just a few minor things. The algorithm is basically correct, but

 if k == len(lst): return lst 

This is the wrong type. The return type is not a list of things, but a list (list of things), so it should be

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

Further

 if k == 0: return [] 

Each list has exactly one non-empty sublist, an empty list, so it should be

 if k == 0: return [[]] 

For the rest

 if k > len(lst): return [] 

is completely correct.

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

This is correct, but can be stated more briefly:

 sub_lst = lst[1:] 

Now, another type of mix-up:

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

That sets.append(a) puts a in one sets slot, you want to merge the two lists, sets = sets + a . And if you need combinations in the order in which the items appear in the list, and not i.append(lst[0]) , you should add [lst[0]] + i to sets in the loop, but this is a tilt issue.

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

Again, don’t add, but concatenate here,

 sets = sets + b 

Answer 5

basically you need to use the following recursion:

f (k, n) = append_to_each (f (k-1, n-1), n) | e (k, p-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