6

I didn't find a better way to phrase this question in the title. If you can, please edit.

I have a list of lists like this:

a = [['a','b'],[1,2]]

now, I'd like a function that spits out all possible combination like this:

[['a',1],['a',2],['b',1],['b',2]]

where nor the number of lists in a is known in advance, nor is the length of each of the sub lists known in advance, but all the combinations that come out should contain 1 item from every sublist.

bigblind
  • 12,539
  • 14
  • 68
  • 123

3 Answers3

14

You need itertools.product():

>>> list(itertools.product(*a))
[('a', 1), ('a', 2), ('b', 1), ('b', 2)]
Sven Marnach
  • 574,206
  • 118
  • 941
  • 841
0

This may be what itertools.product() (which Sven mentions) does:

def combs(list1, list2):
    results = []
    for x in list1:
        for y in list2:
            l.append([x,y])
    return results
Anko - inactive in protest
  • 6,036
  • 5
  • 35
  • 47
  • That would work if I always only had 2 sublists, as in the example `[[1,2],['a','b']], and then you'd just pass the two sub lists to this function, but this is not the case, the list might as well be `[['a','b','c'],[1,2],[{},[],()]]`, so now we have 3 sublists, so what we'd need is a function where you multiply a variable number of lists. – bigblind Nov 23 '11 at 22:56
  • Ah, I assumed from your example it would always be pairs. I don't have a better suggestion then. – Anko - inactive in protest Nov 24 '11 at 16:20
0

Here is a solution using recursion, combs_r has accum digest head (the next list in line) to produce a fatter accum0, then and calls itself ("recursion") with tail (the remaining lists) and the now fatter accum accum0.

Might be heavy user of memory as each call to combs_r adds a new namespace, until the end when it all unwinds. Person more knowlegable in Python internals might comment on this.

Pays to learn prolog, IMHO.

def combs(ll):
    if len(ll) == 0:
        return []
    if len(ll) == 1:
         return [[item] for item in ll[0]]
    elif len(ll) == 2:
        return lmul(ll[0], [[item] for item in ll[1]])
    else:
        return combs_r(ll[1:], ll[0])

def combs_r(ll, accum):
    head = ll[0]
    tail = ll[1:]
    accum0 = []
    accum0 = lmul(head, accum)
    if len(tail) == 0:
        return accum0
    else:
        return combs_r(tail, accum0)

def lmul(head, accum):
    accum0 = []
    for ah in head:
        for cc in accum:
            #cc will be reused for each ah, so make a clone to mutate
            cc0 = [x for x in cc]
            cc0.append(ah)
            accum0.append(cc0)
    return accum0

sampleip = [['a','b','c'],[1,2], ['A', 'B']]
sampleip2 = [['a','b','c'],[1,2]]
sampleip1 = [['a','b','c']]
sampleip0 = []
print combs(sampleip0)
print combs(sampleip1)
print combs(sampleip2)
print combs(sampleip)
Nathan Finstein
  • 86
  • 2