python combinations of multiple list

Question

Is there any pythonic method to generate combinations between multiple list? (similar to Cartesian product but more complicated)

Example:

a = [1, 2, 3]
b = [4, 5, 6]
c = [7, 8, 9]
# ...
# there are more than 3 lists

Expected output:

1. [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
2. [(1, 4, 8), (2, 5, 7), (3, 6, 9)]
3. [(1, 4, 9), (2, 5, 7), (3, 6, 8)]
4. [(1, 5, 7), (2, 4, 8), (3, 6, 9)]
5. ...

Update:

Thanks for the quick reply~!!

To clarify the question:

The result are all non-repeated combinations of Cartesian product of list a, b, c.

It can be done by another ugly method:

1) Generate the whole list of Cartesian product

from itertools import product, combinations, chain
t = list(product(a, b, c))

2) Using combinations to generate all possible results

p = list(combinations(t, 3))

3) Filter the repeated conditions

cnt = len(list(chain(a, b, c)))
f = [x for x in p if len(set(chain(*x))) == cnt]

Update2:

Expected result generated by ugly method:

((1, 4, 7), (2, 5, 8), (3, 6, 9))
((1, 4, 7), (2, 5, 9), (3, 6, 8))
((1, 4, 7), (2, 6, 8), (3, 5, 9))
((1, 4, 7), (2, 6, 9), (3, 5, 8))
((1, 4, 8), (2, 5, 7), (3, 6, 9))
((1, 4, 8), (2, 5, 9), (3, 6, 7))
((1, 4, 8), (2, 6, 7), (3, 5, 9))
((1, 4, 8), (2, 6, 9), (3, 5, 7))
((1, 4, 9), (2, 5, 7), (3, 6, 8))
((1, 4, 9), (2, 5, 8), (3, 6, 7))
((1, 4, 9), (2, 6, 7), (3, 5, 8))
((1, 4, 9), (2, 6, 8), (3, 5, 7))
((1, 5, 7), (2, 4, 8), (3, 6, 9))
((1, 5, 7), (2, 4, 9), (3, 6, 8))
((1, 5, 7), (2, 6, 8), (3, 4, 9))
((1, 5, 7), (2, 6, 9), (3, 4, 8))
((1, 5, 8), (2, 4, 7), (3, 6, 9))
((1, 5, 8), (2, 4, 9), (3, 6, 7))
((1, 5, 8), (2, 6, 7), (3, 4, 9))
((1, 5, 8), (2, 6, 9), (3, 4, 7))
((1, 5, 9), (2, 4, 7), (3, 6, 8))
((1, 5, 9), (2, 4, 8), (3, 6, 7))
((1, 5, 9), (2, 6, 7), (3, 4, 8))
((1, 5, 9), (2, 6, 8), (3, 4, 7))
((1, 6, 7), (2, 4, 8), (3, 5, 9))
((1, 6, 7), (2, 4, 9), (3, 5, 8))
((1, 6, 7), (2, 5, 8), (3, 4, 9))
((1, 6, 7), (2, 5, 9), (3, 4, 8))
((1, 6, 8), (2, 4, 7), (3, 5, 9))
((1, 6, 8), (2, 4, 9), (3, 5, 7))
((1, 6, 8), (2, 5, 7), (3, 4, 9))
((1, 6, 8), (2, 5, 9), (3, 4, 7))
((1, 6, 9), (2, 4, 7), (3, 5, 8))
((1, 6, 9), (2, 4, 8), (3, 5, 7))
((1, 6, 9), (2, 5, 7), (3, 4, 8))
((1, 6, 9), (2, 5, 8), (3, 4, 7))

do you want an iterator ? then `itertools.product(*args)`is what you are looking for. just place your lists as `arg`. — Marvin Taschenberger, Jul 25 '17 at 16:02
if you want the cartesian in a mathematical sense look into `SymPy` and it's `FiniteSet` — Marvin Taschenberger, Jul 25 '17 at 16:05
@MosesKoledoye: The OP has put in an ellipsis to indicate that the list of outputs is incomplete. — Bill Bell, Jul 25 '17 at 16:16
Your question isn't completely clear. How many lines of output do you expect for that input data? If you want the Cartesian product of each permutation of a, b, and c, that'd result in 216 lines. — PM 2Ring, Jul 25 '17 at 16:28
I've written code for @PM2Ring's suggestion. If that's the case then please reword the question. — Antti Haapala -- Слава Україні, Jul 25 '17 at 17:00
@PM2Ring Thanks for your reply! But the number is 36 (I guess) instead of 216, since I use combination instead of permutation. — Vincent Li, Jul 25 '17 at 18:50
36? so in essence you're not making a permutation of the *first* — Antti Haapala -- Слава Україні, Jul 25 '17 at 19:44
FWIW, you can make your original algorithm consume less RAM by not building lists from the outputs of `combinations` and `products`, eg `cnt = sum(map(len, (a, b, c))); p = combinations(product(a, b, c), 3); f = [x for x in p if len(set(chain.from_iterable(x))) == cnt]`. But this still generates those 2925 combinations, so it's still very inefficient compared to Antti's algorithm. — PM 2Ring, Jul 25 '17 at 20:52
@PM2Ring, thanks for your suggestion. It does reduce the consumption of RAM. I am looking for an algorithm which does not generate 2925 combinations. Antti's algorithm does not create a large combinations set, which is very nice. But the output is not the expected result.. — Vincent Li, Jul 26 '17 at 01:27

score 2 · Answer 1 · edited Jul 25 '17 at 16:38

2

You can use product from itertools for all combinations

>>> from itertools import product
>>> a = [1, 2, 3]
>>> b = [4, 5, 6]
>>> c = [7, 8, 9]
>>> A = [a,b,c]
>>> prod = list(product(*A))
>>> print(prod)

Expected output:

[(1, 4, 7), (1, 4, 8), (1, 4, 9), (1, 5, 7), (1, 5, 8), (1, 5, 9), (1, 6, 7), (1, 6, 8), (1, 6, 9), (2, 4, 7), (2, 4, 8), (2, 4, 9), (2, 5, 7), (2, 5, 8), (2, 5, 9), (2, 6, 7), (2, 6, 8), (2, 6, 9), (3, 4, 7), (3, 4, 8), (3, 4, 9), (3, 5, 7), (3, 5, 8), (3, 5, 9), (3, 6, 7), (3, 6, 8), (3, 6, 9)]

edited Jul 25 '17 at 16:38

pylang

40,867
14
129
121

answered Jul 25 '17 at 16:16

dheeraj .A

1,073
7
6

1

This does not look like the output that OP is expecting. – Akavall Jul 25 '17 at 16:36
I think you have it if you add `list(itertools.permutations(prod, 3))` for the final result. – pylang Jul 25 '17 at 16:37

Antti Haapala -- Слава Україні · Accepted Answer · 2017-07-26T01:46:17.983

What you want are not combinations but indeed permutations. 3 elements have 6 permutations, a Cartesian product of 2 sets of permutations has 36. PM 2Ring originally suspected that you want all 3 of these permuted since your question didn't tell otherwise. If the code in your question produces the desired output, it means you want b and c permuted but not a. Initially I wrote code that calculated the permutations for all of a, b and c. However, since a doesn't need to be permuted, we'll just wrap it in a list. This gets us very close to the desired output:

import itertools as it

a = [1, 2, 3]
b = [4, 5, 6]
c = [7, 8, 9]

for i in it.product([tuple(a)], it.permutations(b), it.permutations(c)):
    print(i)

The output is 36 lines that start with

((1, 2, 3), (4, 5, 6), (7, 8, 9))
((1, 2, 3), (4, 5, 6), (7, 9, 8))
((1, 2, 3), (4, 5, 6), (8, 7, 9))

It is already almost the same format that you want but with indexes transposed so o[x][y] would match o[y][x] of your desired output. We use some zip magic to transpose them. As a plus, this function now works for any number of arguments:

import itertools as it

a = [1, 2, 3]
b = [4, 5, 6]
c = [7, 8, 9]

def funnyperms(first, *rest):
    for i in it.product([first], *(it.permutations(j) for j in rest)):
        yield tuple(zip(*i))

for i in funnyperms(a, b, c):
    print(i)

The output is

((1, 4, 7), (2, 5, 8), (3, 6, 9))
((1, 4, 7), (2, 5, 9), (3, 6, 8))
((1, 4, 8), (2, 5, 7), (3, 6, 9))
((1, 4, 8), (2, 5, 9), (3, 6, 7))
((1, 4, 9), (2, 5, 7), (3, 6, 8))
((1, 4, 9), (2, 5, 8), (3, 6, 7))
((1, 4, 7), (2, 6, 8), (3, 5, 9))
((1, 4, 7), (2, 6, 9), (3, 5, 8))
((1, 4, 8), (2, 6, 7), (3, 5, 9))
((1, 4, 8), (2, 6, 9), (3, 5, 7))
((1, 4, 9), (2, 6, 7), (3, 5, 8))
((1, 4, 9), (2, 6, 8), (3, 5, 7))
((1, 5, 7), (2, 4, 8), (3, 6, 9))
((1, 5, 7), (2, 4, 9), (3, 6, 8))
((1, 5, 8), (2, 4, 7), (3, 6, 9))
((1, 5, 8), (2, 4, 9), (3, 6, 7))
((1, 5, 9), (2, 4, 7), (3, 6, 8))
((1, 5, 9), (2, 4, 8), (3, 6, 7))
((1, 5, 7), (2, 6, 8), (3, 4, 9))
((1, 5, 7), (2, 6, 9), (3, 4, 8))
((1, 5, 8), (2, 6, 7), (3, 4, 9))
((1, 5, 8), (2, 6, 9), (3, 4, 7))
((1, 5, 9), (2, 6, 7), (3, 4, 8))
((1, 5, 9), (2, 6, 8), (3, 4, 7))
((1, 6, 7), (2, 4, 8), (3, 5, 9))
((1, 6, 7), (2, 4, 9), (3, 5, 8))
((1, 6, 8), (2, 4, 7), (3, 5, 9))
((1, 6, 8), (2, 4, 9), (3, 5, 7))
((1, 6, 9), (2, 4, 7), (3, 5, 8))
((1, 6, 9), (2, 4, 8), (3, 5, 7))
((1, 6, 7), (2, 5, 8), (3, 4, 9))
((1, 6, 7), (2, 5, 9), (3, 4, 8))
((1, 6, 8), (2, 5, 7), (3, 4, 9))
((1, 6, 8), (2, 5, 9), (3, 4, 7))
((1, 6, 9), (2, 5, 7), (3, 4, 8))
((1, 6, 9), (2, 5, 8), (3, 4, 7))

Storing these into a set and comparing with the values produced by your method proves that they have identical output:

print(set(funnyperms(a, b, c)) == set(f))

prints True, Q.E.D.

Thanks for your answer! It's a pretty nice method, but the result is different (elements from input should be separated into different). I updated the question with expected result. Is there any algorithm to produce that result? — Vincent Li, Jul 26 '17 at 01:38
what do you mean? As I say there, my second code produces a set of tuples that is identical to what you provided... — Antti Haapala -- Слава Україні, Jul 26 '17 at 01:44
Oops, sorry I missed your second code. This result is exactly what I wanted. That's awesome!! Thank you so much for you answer! — Vincent Li, Jul 26 '17 at 02:30

python combinations of multiple list

2 Answers2

Linked