0

I am currently using python to execute my code. My input into this function is a list within a list like [ [1,2,3],[4,5],[6,7,8,9] ] The goal is to iterate and create all the possible combinations for each list.

The only way I have it in my mind is to do multiple for loops on each sublist within the master list. Each combination must have at least one element from each sublist so since there are 3 sublists, all combinations must have 3 elements. for a in [1,2,3]: for b in [4,5]: for c in [6,7,8,9]: l.append([a,b,c])

So one combination would be [1,4,6],[1,4,7],[1,4,8],[1,4,9]. And the next loop with be [1,5,6]..[1,5,7]...and so forth.

This works but my problem is that I don't know how many sublists will be in the master list (input) so I cant just keep writing for loops indefinitely. I know there must be a way to write a recursive function but I have never done this and don't know how it works. I don't think it should be too difficult but can someone show me the algorithm to accomplish this please?

Thank you so much!!

Allen Lee
  • 19
  • 3
  • @Allen Lee I think this is a duplicate question unless stdlib cannot be used in your case. – satoru Feb 15 '14 at 00:50
  • Why are these question's still getting answered? There's gonna be hundreds duplicates of this. and the answer is always to just use itertools. And a simple google search for "python combinations" will give you the link to itertools documentation as the first link. And then 5-10 links to SO with solutions. – M4rtini Feb 15 '14 at 01:07
  • @M4rtini a big part of the problem is that people who want to do this won't know the necessary terminology, so they won't pick up on `itertools.product` since they don't know that they want a Cartesian product. People with combinatorics problems generally think everything is a matter of "combinations". – Karl Knechtel Feb 18 '23 at 16:41

2 Answers2

3

If you are trying to learn about recursion, think this way: The combinations of all the lists consist of taking one item at a time from the first list and prepending this item to all the combinations of the remaining lists.

This way you get

def combinations(rest, prefix = [], result = []):
    if rest:
        first = rest.pop()
        for item in first:
            prefix.append(item)
            combinations(rest, prefix, result)
            prefix.pop()
        rest.append(first)
    else:
        result.append(list(reversed(prefix)))
    return result

NB I am far from a Python expert. It's likely there is a more elegant way to code this. Note that because I'm pushing and popping at the ends of lists I need to reverse the final results. The advantage of this is that it's fast and should produce no garbage.

In Idle:

>>> combinations([ [1,2,3],[4,5],[6,7,8,9] ] )
[[1, 4, 6], [2, 4, 6], [3, 4, 6], [1, 5, 6], [2, 5, 6], [3, 5, 6], 
 [1, 4, 7], [2, 4, 7], [3, 4, 7], [1, 5, 7], [2, 5, 7], [3, 5, 7], 
 [1, 4, 8], [2, 4, 8], [3, 4, 8], [1, 5, 8], [2, 5, 8], [3, 5, 8], 
 [1, 4, 9], [2, 4, 9], [3, 4, 9], [1, 5, 9], [2, 5, 9], [3, 5, 9]]
Gene
  • 46,253
  • 4
  • 58
  • 96
2

Try using the itertools library:

import itertools
arr = [[1,2], [3,4], [5,6]]

list(itertools.product(*arr))
# => [(1, 3, 5), (1, 3, 6), (1, 4, 5), (1, 4, 6), (2, 3, 5), (2, 3, 6), (2, 4, 5), (2, 4, 6)]
tckmn
  • 57,719
  • 27
  • 114
  • 156