Permutations that don't repeat python

Question

Is there a way in Python to generate all the permutations of a list without getting two copies of the same list (due to identical elements within the list).

For example, the list ["up","up"] should only generate the list ["up","up"] and not twice.

Another example would be ["up", "up", "right"] only returns:

["up", "up", "right"]
["up", "right", "up"]
["right", "up", "up"]

and not the following:

["up", "up", "right"]
["up", "right", "up"]
["right", "up", "up"]
["up", "up", "right"]
["up", "right", "up"]
["right", "up", "up"]

For example this script does not give the desired list.

>>> import itertools
>>> a = list(itertools.permutations(["up","up","down"]))
>>> print a
[('up', 'up', 'down'), ('up', 'down', 'up'), ('up', 'up', 'down'), ('up', 'down', 'up'), ('down', 'up', 'up'), ('down', 'up', 'up')]

Note: how can I make this faster with larger lists of size 20 or greater?

• Monte Carlo: No I just need to know how many distinct permutations for 20 ups and 20 downs. What's the best way to do this? Python has been chugging away at for 42:34.20 now. There has to be a better way to do this.
• DSM: Ah. We call this the XY problem. Apparently your real question is "how many distinct tuples are there with 20 ups and 20 downs?" -- which is one simple formula, no Python required -- but instead of asking about your real problem, you asked "how do I make creating a long list of the permutations faster?"
• Monte Carlo: @DSM What is the formula? How did you solve the 15, 15 for distinct tuples?

Answer 1

You can just do

print list(set(a))

DEMO:

>>> import itertools
>>> a = list(itertools.permutations(["up","up","down"]))
>>> a
[('up', 'up', 'down'), ('up', 'down', 'up'), ('up', 'up', 'down'), ('up', 'down', 'up'), ('down', 'up', 'up'), ('down', 'up', 'up')]
>>> set(a)
set([('up', 'up', 'down'), ('down', 'up', 'up'), ('up', 'down', 'up')])
>>> list(set(a))
[('up', 'up', 'down'), ('down', 'up', 'up'), ('up', 'down', 'up')]
>>> 

Answer 2

You could get a set of the results:

>>> set(itertools.permutations(a))
set([('up', 'up', 'right'), ('right', 'up', 'up'), ('up', 'right', 'up')])

This ensures you don't get duplicates in your output.

You can convert a set back to a list with list() of course.

• Monte Carlo: Is there a way to make this faster? My list starts at 30 units long, and my code just seems to hang, and my cpu usage goes off the chart.

Answer 3

This isn't a Python question, it's a math question. (In the comments it turned out that the OP isn't after the list itself, but merely the count.)

If you have 30 slots to be filled with 15 "up"s and 15 "down"s, then you need to choose 15 distinct locations out of 30 possibles to place the "up"s, and then the rest are forced to be "down".

Choosing 15 distinct numbers out of 30 is 30 choose 15, or 30!/((15!)*((30-15)!)):

>>> from math import factorial
>>> factorial(30)/factorial(15)/factorial(30-15)
155117520L

We can check this expression manually for a smaller list:

>>> from itertools import permutations
>>> len(set(permutations(["up"]*7+["down"]*3)))
120
>>> factorial(10)/factorial(7)/factorial(10-7)
120