Monte Carlo
Monte Carlo

Reputation: 457

Permutations that don't repeat python

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

Answers (3)

DSM
DSM

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

Simeon Visser
Simeon Visser

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

karthikr
karthikr

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

Related Questions