In Python, it is quite simple to produce all permutations of a list using the itertools
module. I have a situation where the sequence I'm using only has two characters (i.e. '1122'
). I want to generate all unique permutations.
For the string '1122'
, there are 6 unique permutations (1122
, 1212
, 1221
, etc), but itertools.permutations
will yield 24 items. It's simple to only record the unique permutations, but it will take much longer than necessary to collect them as all 720 items are considered.
Is there a function or module that accounts for repeated elements when generating permutations so I don't have to write my own?
This web page looks promising.
def next_permutation(seq, pred=cmp):
"""Like C++ std::next_permutation() but implemented as
generator. Yields copies of seq."""
def reverse(seq, start, end):
# seq = seq[:start] + reversed(seq[start:end]) + \
# seq[end:]
end -= 1
if end <= start:
return
while True:
seq[start], seq[end] = seq[end], seq[start]
if start == end or start+1 == end:
return
start += 1
end -= 1
if not seq:
raise StopIteration
try:
seq[0]
except TypeError:
raise TypeError("seq must allow random access.")
first = 0
last = len(seq)
seq = seq[:]
# Yield input sequence as the STL version is often
# used inside do {} while.
yield seq[:]
if last == 1:
raise StopIteration
while True:
next = last - 1
while True:
# Step 1.
next1 = next
next -= 1
if pred(seq[next], seq[next1]) < 0:
# Step 2.
mid = last - 1
while not (pred(seq[next], seq[mid]) < 0):
mid -= 1
seq[next], seq[mid] = seq[mid], seq[next]
# Step 3.
reverse(seq, next1, last)
# Change to yield references to get rid of
# (at worst) |seq|! copy operations.
yield seq[:]
break
if next == first:
raise StopIteration
raise StopIteration
>>> for p in next_permutation([int(c) for c in "111222"]):
... print p
...
[1, 1, 1, 2, 2, 2]
[1, 1, 2, 1, 2, 2]
[1, 1, 2, 2, 1, 2]
[1, 1, 2, 2, 2, 1]
[1, 2, 1, 1, 2, 2]
[1, 2, 1, 2, 1, 2]
[1, 2, 1, 2, 2, 1]
[1, 2, 2, 1, 1, 2]
[1, 2, 2, 1, 2, 1]
[1, 2, 2, 2, 1, 1]
[2, 1, 1, 1, 2, 2]
[2, 1, 1, 2, 1, 2]
[2, 1, 1, 2, 2, 1]
[2, 1, 2, 1, 1, 2]
[2, 1, 2, 1, 2, 1]
[2, 1, 2, 2, 1, 1]
[2, 2, 1, 1, 1, 2]
[2, 2, 1, 1, 2, 1]
[2, 2, 1, 2, 1, 1]
[2, 2, 2, 1, 1, 1]
>>>
2017-08-12
Seven years later, here is a better algorithm (better for clarity):
from itertools import permutations
def unique_perms(series):
return {"".join(p) for p in permutations(series)}
print(sorted(unique_perms('1122')))