Combination of loop with recursion function

Question

Having the following code:

def choose_sets(lst,k):
 if k == 0:
      return [[]]
 if len(lst) == k:
      return [lst]
 else:
      return choose_sets(lst[1:],k)+[[lst[0]]+i for i in choose_sets(lst[1:],k-1)]

How does i for i in choose_sets(lst[1:],k-1) work? Is it possible to give up on the loop and instead to write this?

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

this function returns list that contains all the different lists at length K that can be created out of the original list's members (the order isn't important)

Have you taken a look at docs.python.org/2/library/itertools.html#itertools.permutations? This might be similar to what you're looking for. — AMacK
– AMacK, Commented Sep 12, 2014 at 3:28
@AMacK But why "i for i in " must be written? Why "choose_sets(lst[1:],k)+[[lst[0]]+choose_sets(lst[1:],k-1)] " isn't enough? — user3227
– user3227, Commented Sep 12, 2014 at 3:34
You really don't want to write something which recursively appends to a list; since appending is itself O(N), that will be O(N^2). Terrible for scalability. Like @AMacK said, read through docs.python.org/2/library/itertools.html#itertools.permutations and pick the right tool for the job. This code is like instant-fail in an interview. — smci
– smci, Commented Sep 12, 2014 at 3:50

Timothy Zhang · Accepted Answer · 2014-09-12 03:45:18Z

i for i in choose_sets(lst[1:],k-1)

yields all the sets whose length is k-1 and does not contain lst[0]. In the other word, we got a list, whose elements are lists with length k-1. Adding lst[0] to each of them, we got all K-length sets that contains lst[0].

Plus choose_sets(lst[1:],k), which yields all K-length sets that does not contain lst[0], we got all K-length sets.

Is it possible to give up on the loop and instead to write this?

No. +[[lst[0]]+choose_sets(lst[1:],k-1)] yields a list whose first element is with length 1 and all other elements are with length k-1, this is obviousely what we expected.

Collectives™ on Stack Overflow

Combination of loop with recursion function

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related