How can I get "permutations with repetitions/replacement" from a list (Cartesian product of a list with itself)?

Question

Suppose I have a list die_faces = [1, 2, 3, 4, 5, 6]. I want to generate all 36 possible results for rolling two dice: (1, 1), (1, 2), (2, 1) etc. If I try using permutations from the itertools standard library:

>>> import itertools
>>> die_faces = [1, 2, 3, 4, 5, 6]
>>> list(itertools.permutations(die_faces, 2))
[(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 3), (2, 4), (2, 5), (2, 6), (3, 1), (3, 2), (3, 4), (3, 5), (3, 6), (4, 1), (4, 2), (4, 3), (4, 5), (4, 6), (5, 1), (5, 2), (5, 3), (5, 4), (5, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5)]

there are only 30 results, missing the ones where the same number comes up on both dice. It seems that it only generates permutations without repetitions. How can I fix this?

Westberg

See also stackoverflow.com/questions/942543 for the case of directly calling a function with the new values. – Icy

list1_permutations = itertools.permutations(list1, len(list2)) - example here – Unstick

more precisely for your input pairs = itertools.permutations(_faces, 2); print(list(pairs)) – Unstick

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)

Pluto

This is an extremely inefficient way of getting 2 dice rolls… Two calls to random.randint would be simpler and more efficient. – Brandwein

Random dice rolls will be much faster when you don't generate all possible pairs: [random.randint(1,6) for i in xrange(2)] – Illstarred

I wasn't actually trying to generate random rolls, just to list all possible rolls. – Westberg

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)

Headrail

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

Eclecticism

This solution looses out on the combinations (2, 1), (3, 2), (3, 1) and similar... In general it leaves out all combinations where the second roll is lower than the first. – Scorn

Maybe not the "right" solution, but the right one for me! Thanks! – Paralyse

have to downvote since @Scorn is right and this can be confusong – Uhland

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)

Lomasi

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

Pileous

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

Aeneid

That does not include duplicates. – Malversation

OP explicitly wants duplicates – Digged