Generate permutations of list with repeated elements

Question

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?

Answer 1

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

Answer 2

More Itertools has a function for this:

more-itertools.distinct_permutations(iterable)

Yields successive distinct permutations of the elements in iterable.

Equivalent to set(permutations(iterable)), except duplicates are not generated and thrown away. For larger input sequences, this is much more efficient.

from more_itertools import distinct_permutations

for p in distinct_permutations('1122'):
    print(''.join(p))

# 2211
# 2121
# 1221
# 2112
# 1212
# 1122

Installation:

pip install more-itertools