Combinations Recursive Algorithm

Question

I need to write a recursive function that calculates all the possible combinations of length "n" in a list, in Python, without importing anything like itertools etc.

So what I have so far is:

if n == 0:
    return [[]]
elif lst == []:
    return []
else:
    rest = subsets(lst[1:], n-1)
    for next in lst:  # Loop through something?
        return lst[0] + rest #Add something?

I seem to be lacking an understanding of how the recursive calls work, can someone explain this to me?

Can you fix up your indenting for us? Click the "edit" button beneath your post. — BlackVegetable, Jul 09 '14 at 00:36
Is your function called `subsets`? If so, can you include the function heading in it? — BlackVegetable, Jul 09 '14 at 00:53
A question that I have asked myself a whole bunch of times. Perhaps start be getting all the combinations of 'n' numbers below the length of the list (including zero) and then getting the elements by index. — RGS, Jul 09 '14 at 00:57
Also: it is important to know if the order of the combinations matter, if you just want unique outputs. Are both [a, b] and [b, a] counted? Or just [a, b]? And say the list is [a, b, c] and you want 2-len subsets. Is [a, a] a valid output? — RGS, Jul 09 '14 at 00:58
@RSerrao's point about whether [a, b] is unique from [b, a] is rather important and enough to render my answer pretty much wrong, depending on the answer. Still, I think if you just write out what you want the recursive calls to look like, then it should mostly write itself. — Josh Berry, Jul 09 '14 at 01:03

RGS · Accepted Answer · 2014-07-10T11:58:34.500

In the absence of the required output specifications, we could write some pseudo-code like this:

def combinations(sub, data_set, items_needed):
    if you dont need, return sub
    for item in data_set:
        append item to sub
        #pop() item from data_set?
        decrease items_needed # added one more, so we need one less
        combinations(new_sub, data_set, items_needed)

Where poping() or not will depend on you wanting (or not) unique items in the subset.

If you say you don't want both [a, b] and [b, a] you would have to also keep track of the index of the last item added, in order to only add new items to create new combinations.

def combinations(sub, data_set, index, still_needed):
    if you dont need any, return
    for i in range(index, len(data_set)):
        append data_set[i] to sub
        decrease still_needed
        combinations(sub, data_set, index+1, still_needed)

Thanks, sorry for not providing the specifications I just needed an explanation of how the algorithm would work, this cleared it up! — Soaps, Jul 09 '14 at 22:29
@BurhanKhalid changed variable name to `data_set`. thanks for the heads-up — RGS, Jul 10 '14 at 11:59

score 0 · Answer 2 · answered Jul 09 '14 at 01:00

0

This sounds dangerously like a homework problem. Why does it have to be recursive, as that just seems bad.

Regardless, recursively what you are doing is going through every element in the list and then appending that to the beginning of every other combination of length n - 1. So, if your list was [1, 2, 3], you are wanting an algorithm where the call stack will look like:

foo([], [1, 2, 3], n) ==
  foo([1], [2, 3], n - 1) +
  foo([2], [1, 3], n - 1) +
  foo([3], [1, 2], n - 1)

Where,

foo([1], [2, 3], n - 1) ==
  foo([1, 2], [3], n - 2) +
  foo([1, 3], [2], n - 2)

etc...

You can terminate the recursive calls whenever you have n == 0, or the middle list is empty. And you just return the first argument.

This all make sense? (I can code it up, if desired. I think if you look at the desired callstacks, it should mostly put itself together.)

answered Jul 09 '14 at 01:00

Josh Berry

356
1
6

You probably don't need the `n` because that can be calculated from the length of one of the lists. – ssm Jul 09 '14 at 01:03
Just bear in mind that since the foo() function is being called recursively, you do the inner call always with `n - 1` – RGS Jul 09 '14 at 01:04
@ssm it is probably better to have a variable holding that value than calling `len(subset)` endless times. – RGS Jul 09 '14 at 01:06
Yeah, writing it as n - 2 is rather misleading. Would it look better as (n - 1) - 1? – Josh Berry Jul 09 '14 at 01:08

score -1 · Answer 3 · answered Jul 09 '14 at 02:04

A useful trick when faced with such a basic question (one that is frequently used as introductory level homework or in some programming interviews) is to look at RosetteCode (From which you, too, can learn to impress your friends with words like "chrestomathy"). For this one, in particular we find:

#/usr/bin/env python
# From: http://rosettacode.org/wiki/Combinations#Python
def comb(m, lst):
if m == 0:
    return [[]]
else:
    return [[x] + suffix for i, x in enumerate(lst)
            for suffix in comb(m - 1, lst[i + 1:])]

... along with implementations in dozens of other languages for comparison.

Another handy site is PLEAC (for the "Programming Language Examples Alike Cookbook" project) ... though it has less academic and leans towards more practical programming tasks.

-1 It is a basic question because he is learning, and getting the answer immediately does not help him with his true objective — Liam McInroy, Jul 09 '14 at 03:16

Combinations Recursive Algorithm

3 Answers3

Linked