Reputation: 457
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?
Upvotes: 1
Views: 363
Reputation: 353059
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
Upvotes: 2
Reputation: 122356
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.
Upvotes: 3
Reputation: 99620
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')]
>>>
Upvotes: 4