recursive solution for kind of combination (in python)

Question

Is there a recursive solution for the following problem: For a given list of lists all combinations of the members of these lists should be calculated, for example:

[list('123'), list('ABCD'), list('ab')]

will produce:

 ['a', 'A', '1']
 ['a', 'A', '2']
 ['a', 'A', '3']
 ['a', 'B', '1']
 ['a', 'B', '2']
 ['a', 'B', '3']
 ['a', 'C', '1']
 ['a', 'C', '2']
 ['a', 'C', '3']
 ['a', 'D', '1']
 ['a', 'D', '2']
 ['a', 'D', '3']
 ['b', 'A', '1']
 ['b', 'A', '2']
 ['b', 'A', '3']
 ['b', 'B', '1']
 ['b', 'B', '2']
 ['b', 'B', '3']
 ['b', 'C', '1']
 ['b', 'C', '2']
 ['b', 'C', '3']
 ['b', 'D', '1']
 ['b', 'D', '2']
 ['b', 'D', '3']

The following iterative program generates the above output:

rec = [list('123'), list('ABCD'), list('ab')]
done = False
vect = [0 for i in rec]
while not done:
    pass
    for j in range(len(rec[0])):
        vect[0] = j
        print [rec[i][vect[i]] for i in range(len(rec))][::-1]
    c = not False
    for k in range(1, len(rec)):
        if c:
            c = (vect[k]+c) >= len(rec[k])
            if c:
                vect[k] = 0
            else:
                vect[k] += 1
    if c:
        done = True

but I am looking for a recursive solution which probably will be shorter and more readable ?

fyi, there's no need for the `list()` around those strings. a string already behaves like a list of its characters (besides being immtuable, but that doesn't matter here). oh, and `not False` should obviously be `True`... — ThiefMaster, Sep 06 '15 at 09:24
Not an answer: The standard library provides [`itertools.product()`](https://docs.python.org/3/library/itertools.html#itertools.product), which includes a Python implementation that's a lot more compact. — Martijn Pieters, Sep 06 '15 at 09:25

hiro protagonist · Answer 1 · 2015-09-06T09:29:55.070

you could try this (not recursive but very compact and probably the most efficient you can do):

from itertools import product

for item in product('123', 'ABCD', 'ab'):
    print(item)

output:

('1', 'A', 'a')
('1', 'A', 'b')
('1', 'B', 'a')
('1', 'B', 'b')
('1', 'C', 'a')
('1', 'C', 'b')
('1', 'D', 'a')
('1', 'D', 'b')
('2', 'A', 'a')
('2', 'A', 'b')
('2', 'B', 'a')
('2', 'B', 'b')
('2', 'C', 'a')
('2', 'C', 'b')
('2', 'D', 'a')
('2', 'D', 'b')
('3', 'A', 'a')
('3', 'A', 'b')
('3', 'B', 'a')
('3', 'B', 'b')
('3', 'C', 'a')
('3', 'C', 'b')
('3', 'D', 'a')
('3', 'D', 'b')

recursive solution for kind of combination (in python)

1 Answers1