Generating permutations with repetitions

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

Answers:

Thank you for visiting the Q&A section on Magenaut. Please note that all the answers may not help you solve the issue immediately. So please treat them as advisements. If you found the post helpful (or not), leave a comment & I’ll get back to you as soon as possible.

Method 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)

Method 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)

Method 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)]

Method 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)

Method 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)), [])

Method 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)))

All methods was sourced from stackoverflow.com or stackexchange.com, is licensed under cc by-sa 2.5, cc by-sa 3.0 and cc by-sa 4.0