Efficient combinations of multiple lists (Python)

Question

I'm trying to figure out the most efficient way to get a sorted list of combinations of the items of multiple lists (the number is not known beforehand) in Python (3). For example, if I have a list of sublists:

a = [[0, 1, 2], [0], [0, 1]]

I expect the following output:

[(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 1), (0, 1, 2)]

At the moment, the best method I have is to use itertools.product() to first generate all possible permutations of the three lists, sort the contents of the permutations, then take the set of those items, and then to finally sort that set:

tuples = it.product(*a)
tuples_sorted = [tuple(sorted(i)) for i in tuples]
output = sorted(set(tuples_sorted))

This works just fine, but I was wondering if there was a more efficient or built-in way of doing this? I can imagine the multiple sorting steps getting really cumbersome for a large number of sublists, or for really long sublists. I'm open to numpy solutions, too.

Why is there no `(0, 1, 0)` element in the output? Is that because it's a permutation of `(0, 0, 1)`? — , Mar 08 '17 at 23:29
That is correct; I'm looking for all possible combinations, not permutations. — itf, Mar 09 '17 at 00:49
I don't understand your point about things getting cumbersome for large numbers: doesn't it remain the same three lines of code? — , Mar 09 '17 at 01:29
The code remains the same, but I'm concerned that the sorting steps will get out of hand (in a non-linear way, for instance) for larger sublists and alphabets. — itf, Mar 09 '17 at 01:39
The fundamental nature of this problem seems complex though. What part of this algorithm seems unnecessarily complex given the problem itself? — Apollys supports Monica, Apr 27 '17 at 18:23

score 1 · Accepted Answer · answered Dec 27 '19 at 20:10

What you are asking for is the sorted Cartesian product of multiple lists. It's done like this:

import itertools
>>> a2 = [list(element) for element in itertools.product(*a)]
>>> for i in range(0,len(a2)):
...     aa = a2[i]
...     aa.sort()
...     a2[i] = tuple(aa)
... 
>>> a3=[ii for n,ii in enumerate(a3) if ii not in a2[:n]]
>>> a3
[(0, 0, 0), (0, 0, 1), (0, 1, 1), (0, 0, 2), (0, 1, 2)]

Adapted from this Cartesian product answer and this unique list answer.

Efficient combinations of multiple lists (Python)

1 Answers1