Calculating subsets of a given list recursively

Question

I want to build a recursive function that finds all the subsets of size 'k' of a given list with length n>=k>=0 and returns a list of those subsets.

example: if the input list is [1,2,3,4] and k = 2 then the function will return [[4,3],[2,4],[2,3],[1,4],[1,3],[1,2]]

notice that different arrangments of list is considered to be the same list.

I think that this kind of recursion should work:

return [lst[0]] + choose_sets(lst[1:],k-1)   ¬¬and¬¬   choose_sets(lst[1:],k)

where choose_sets(lst,k) is the function.

Meaning:

input : [1,2,3,4] , k=3

calls:

[1] + [2,3,4],k=2 and [2,3,4], k=3

and so on...

can anyone guide me as to how I should call those 2 recursive calls 'at the same time' ? and what should my 'exiting term' be?

Thanks.

Unless this is an exercise, just use itertools.combinations(). — Thomas
– Thomas, Commented Apr 25, 2013 at 18:20
Is this homework or for fun? Because if it is a real-life problem, there is a standard library function for that. — Lev Levitsky
– Lev Levitsky, Commented Apr 25, 2013 at 18:20
this is indeed homework, I cant use itertools. @KarolyHorvath : how can i call them sequentially? can you please be more specific. If i call one of them then the function will just exit and never get to the other "return". — Matthew D
– Matthew D, Commented Apr 25, 2013 at 18:21

Itay Karo · Accepted Answer · 2013-04-25 19:34:06Z

2

Suppose you have a list of size n and you need all subsets of size k.
This is basically the same as:

For each element of the list, create a new list without the element,
in the new list, find all the subsets of size k-1 (this is the recursive call),
and add the remove element to all the lists.

Now... this solution will have repetitions, for example, in the example you gave, you'll get both [4, 1] and [1, 4]. But it can be changed a little so that it will not create duplicate results.

edit
to handle duplications

def choose_sets(l, k):
  if k == 0:
    return [[]]
  if len(l) == 0:
    return []
  l2 = l[1:]
  subsets = choose_sets(l2, k-1)
  for s in subsets:
    s.append(l[0])
  return subsets+ choose_sets(l2, k)

edited Apr 25, 2013 at 19:34

answered Apr 25, 2013 at 18:29

Itay Karo

18.4k4 gold badges43 silver badges59 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Matthew D Over a year ago

isn't this horribly inefficient? to create lets say 50 new lists if there are 50 elements in the list and then recursive call it over and over again? plus, I dont understand how can i create all those lists exactly and in the end, how do i handle duplicates?

Rushy Panchal Over a year ago

@user2263215 Recursion is rarely the most efficient method, but it is often the most elegant.

Tam211 Over a year ago

When I run this code I get this error: AttributeError: 'int' object has no attribute 'append

Rajesh Kumar · Accepted Answer · 2013-04-25 20:10:25Z

0

b = []

def abc(a,k):
    if len(a)==k:
        b.append(a)
        return b

    b.extend([a[:k-1]+[i] for i in a[k-1:]])    
    return abc(a[1:],k)


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

answered Apr 25, 2013 at 20:10

Rajesh Kumar

1,3084 gold badges15 silver badges31 bronze badges

3 Comments

Cristian Ciupitu Over a year ago

You're using a global variable.

Cristian Ciupitu Over a year ago

I didn't say that it's incorrect, it's just that global variables are bad practice.

Tam211 Over a year ago

This code doesn't return the correct answer for abc([1,2,3,4,5],2)

Collectives™ on Stack Overflow

Calculating subsets of a given list recursively

2 Answers 2

3 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related