multiset combinatorics generation

Question

I came across the following problem.

Is there a fast python built-in method to do the following:

Input: sets {1,2}, {3,4}, {6,7,8}

Output: sets {1,3,6}, {1,3,7}, {1,3,8}, {1,4,6}, {1,4,7}, {1,4,8}, {2,3,6}, {2,3,7}, {2,3,8}, {2,4,6}, {2,4,7}, {2,4,8}

Thanks!

score 2 · Accepted Answer · answered Mar 01 '18 at 19:11

Here is one way to do it:

>>> map(set, itertools.product({1,2}, {3,4}, {6,7,8}))
[set([8, 1, 3]), set([1, 3, 6]), set([1, 3, 7]), set([8, 1, 4]), set([1, 4, 6]), set([1, 4, 7]), set([8, 2, 3]), set([2, 3, 6]), set([2, 3, 7]), set([8, 2, 4]), set([2, 4, 6]), set([2, 4, 7])]

Note that sets are unordered. If you need to preserve ordering, work with lists or tuples:

>>> map(tuple, itertools.product((1,2), (3,4), (6,7,8)))
[(1, 3, 6), (1, 3, 7), (1, 3, 8), (1, 4, 6), (1, 4, 7), (1, 4, 8), (2, 3, 6), (2, 3, 7), (2, 3, 8), (2, 4, 6), (2, 4, 7), (2, 4, 8)]

This readily generalized to a variable number of sets or other collections:

>>> coll = ((1,2), (3,4), (6,7,8))
>>> map(tuple, itertools.product(*coll))
[(1, 3, 6), (1, 3, 7), (1, 3, 8), (1, 4, 6), (1, 4, 7), (1, 4, 8), (2, 3, 6), (2, 3, 7), (2, 3, 8), (2, 4, 6), (2, 4, 7), (2, 4, 8)]

Thanks for the code. How can we see the implementation of the product function? — M.M, Mar 01 '18 at 19:16
Here (it's written in C): https://hg.python.org/cpython/file/b0866382064f/Modules/itertoolsmodule.c#l1813 — NPE, Mar 01 '18 at 19:22

score 1 · Answer 2 · answered Mar 01 '18 at 19:11

a = set([1,2])
b = set([3,4])
c = set([6,7,8])

print [set([x, y, z]) for x in a for y in b for z in c]
#[set([8, 1, 3]), set([1, 3, 6]), set([1, 3, 7]), set([8, 1, 4]), set([1, 4, 6]), set([1, 4, 7]), set([8, 2, 3]), set([2, 3, 6]), set([2, 3, 7]), set([8, 2, 4]), set([2, 4, 6]), set([2, 4, 7])]

score 1 · Answer 3 · answered Mar 01 '18 at 19:13

>>> from itertools import product
>>> list(product([1,2],[3,4,5],[6,7,8]))
[(1, 3, 6), (1, 3, 7), (1, 3, 8), (1, 4, 6), (1, 4, 7), (1, 4, 8), (1, 5, 6), (1, 5, 7), (1, 5, 8), (2, 3, 6), (2, 3, 7), (2, 3, 8), (2, 4, 6), (2, 4, 7), (2, 4, 8), (2, 5, 6), (2, 5, 7), (2, 5, 8)]

multiset combinatorics generation

3 Answers3