Generating permutations with repetitions

Question

I know about itertools, but it seems it can only generate permutations without repetitions.

For example, I'd like to generate all possible dice rolls for 2 dice. So I need all permutations of size 2 of [1, 2, 3, 4, 5, 6] including repetitions: (1, 1), (1, 2), (2, 1)... etc

If possible I don't want to implement this from scratch

Answer 1

You are looking for the Cartesian Product.

In mathematics, a Cartesian product (or product set) is the direct product of two sets.

In your case, this would be {1, 2, 3, 4, 5, 6} x {1, 2, 3, 4, 5, 6}. itertools can help you there:

import itertools
x = [1, 2, 3, 4, 5, 6]
[p for p in itertools.product(x, repeat=2)]
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 2), (2, 3), 
 (2, 4), (2, 5), (2, 6), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), 
 (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (5, 1), (5, 2), (5, 3), 
 (5, 4), (5, 5), (5, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)]

To get a random dice roll (in a totally inefficient way):

import random
random.choice([p for p in itertools.product(x, repeat=2)])
(6, 3)

Answer 2

You're not looking for permutations - you want the Cartesian Product. For this use product from itertools:

from itertools import product
for roll in product([1, 2, 3, 4, 5, 6], repeat = 2):
    print(roll)

Answer 3

In python 2.7 and 3.1 there is a itertools.combinations_with_replacement function:

>>> list(itertools.combinations_with_replacement([1, 2, 3, 4, 5, 6], 2))
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 3), (2, 4), 
 (2, 5), (2, 6), (3, 3), (3, 4), (3, 5), (3, 6), (4, 4), (4, 5), (4, 6),
 (5, 5), (5, 6), (6, 6)]

Answer 4

In this case, a list comprehension is not particularly needed.

Given

import itertools as it


seq = range(1, 7)
r = 2

Code

list(it.product(seq, repeat=r))

---

Details

Unobviously, Cartesian product can generate subsets of permutations. However, it follows that:

• with replacement: produce all permutations n^r via product
• without replacement: filter from the latter

Permutations with replacement, n^r

[x for x in it.product(seq, repeat=r)]

Permutations without replacement, n!

[x for x in it.product(seq, repeat=r) if len(set(x)) == r]

# Equivalent
list(it.permutations(seq, r))  

Consequently, all combinatoric functions could be implemented from product:

• combinations_with_replacement implemented from product
• combinations implemented from permutations, which can be implemented with product (see above)

Answer 5

I think I found a solution using only lambdas, map and reduce.

product_function = lambda n: reduce(lambda x, y: x+y, map(lambda i: list(map(lambda j: (i, j), np.arange(n))), np.arange(n)), [])

Essentially I'm mapping a first lambda function that given a row, iterates the columnns

list(map(lambda j: (i, j), np.arange(n)))

then this is used as the output of a new lambda function

lambda i:list(map(lambda j: (i, j), np.arange(n)))

which is mapped across all the possible rows

map(lambda i: list(map(lambda j: (i, j), np.arange(n))), np.arange(m))

and then we reduce all the resulting lists into one.

even better

Can also use two different numbers.

prod= lambda n, m: reduce(lambda x, y: x+y, map(lambda i: list(map(lambda j: (i, j), np.arange(m))), np.arange(n)), [])

Answer 6

First, you'll want to turn the generator returned by itertools.permutations(list) into a list first. Then secondly, you can use set() to remove duplicates Something like below:

def permutate(a_list):
    import itertools
    return set(list(itertools.permutations(a_list)))