CODEWITHSUNDEEP
pythonpermutation
drzbir
drzbir

Reputation: 449

How to generate all possible combinations from all permutations?

I have a list of all permutations of K elements in Python like this:

import itertools
perms = list(itertools.permutations(range(K), K))

I would like to generate a matrix (or list) M of all possible combinations of these permutations perms. Each element of this matrix (or list) is of size N. How can I do this?

For example, for K=2, I would get perms=[(0, 1), (1, 0)]. For N=3, I would like to have:

M = [ [(0, 1), (0, 1), (0, 1)],
      [(0, 1), (0, 1), (1, 0)],
      [(0, 1), (1, 0), (0, 1)],
      [(0, 1), (1, 0), (1, 0)],
      [(1, 0), (0, 1), (0, 1)],
      [(1, 0), (0, 1), (1, 0)],
      [(1, 0), (1, 0), (0, 1)],
      [(1, 0), (1, 0), (1, 0)] ]

M is a list that has 8 lists. Each list is of size N=3 and contains elements from perms.

For N=2, I would like to have:

M = [ [(0, 1), (0, 1)],
      [(0, 1), (1, 0)],
      [(1, 0), (0, 1)],
      [(1, 0), (1, 0)] ]

And for N=1, I would like to have:

M = [ [(0, 1), (1, 0)] ] = perms

I do not know if I formulate my problem correctly (I think it can be re-formulated more clearly than this).

Upvotes: 2

Views: 213

Answers (2)

Jared Goguen
Jared Goguen

Reputation: 9008

You can use product from itertools.

from itertools import permutations, product

perms = permutations(range(2))
cartesian_tuples = product(perms, repeat=3)

# (((0, 1), (0, 1), (0, 1)),
#  ((0, 1), (0, 1), (1, 0)),
#  ((0, 1), (1, 0), (0, 1)),
#  ((0, 1), (1, 0), (1, 0)),
#  ((1, 0), (0, 1), (0, 1)),
#  ((1, 0), (0, 1), (1, 0)),
#  ((1, 0), (1, 0), (0, 1)),
#  ((1, 0), (1, 0), (1, 0)))

You can manually convert individual parts into lists if you need to iterate over anything more than once. The current structure is composed of generators that will be exhausted after one iteration and cannot be used again. If you want nested lists:

cartesian_tuples = map(list, list(product(perms, repeat=3)))

# [[(0, 1), (0, 1), (0, 1)],
#  [(0, 1), (0, 1), (1, 0)],
#  [(0, 1), (1, 0), (0, 1)],
#  [(0, 1), (1, 0), (1, 0)],
#  [(1, 0), (0, 1), (0, 1)],
#  [(1, 0), (0, 1), (1, 0)],
#  [(1, 0), (1, 0), (0, 1)],
#  [(1, 0), (1, 0), (1, 0)]]

In Python 3.X, you will have to wrap this in another list call because map(...) returns a map object.

cartesian_tuples = list(map(list, list(product(perms, repeat=3))))

Or, you can avoid all that nonsense and use a list comprehension.

cartesian_tuples = [[perm for perm in prod] for prod in product(perms, repeat=3)]

But it might just be better to create a new iterator each time you need one.

def product_of_permutations(n, k):
    return product(permutations(range(k)), repeat=n)

Upvotes: 3

MSeifert
MSeifert

Reputation: 152870

Thinking about it there might be a very simple way to get your desired result using itertools.combinations together with set:

import itertools
K = 2
N = 3
perms = list(itertools.permutations(range(K), K))
# The order matters so we need to copy the list N times
perms = perms*N 
# Create the combinations
combs = itertools.combinations(perms, N)
# Only keep unique combinations
M = set(combs)

If you want to have it as list of lists use:

M = [list(i) for i in M]

returns then

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

Upvotes: 3

Related Questions