Generate permutations of list with repeated elements

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 permutationsdef unique_perms(series):    return {"".join(p) for p in permutations(series)}print(sorted(unique_perms('1122')))

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 notgenerated and thrown away. For larger input sequences, this is muchmore efficient.

from more_itertools import distinct_permutationsfor p in distinct_permutations('1122'):    print(''.join(p))# 2211# 2121# 1221# 2112# 1212# 1122

Installation:

pip install more-itertools

Using set makes solution simpler. Strings with repeated chars, andnon repeated,used as input.

from itertools import permutationsdef perm(s):    return set(permutations(s))        l = '1122'        perm(l)      {('1', '1', '2', '2'),     ('1', '2', '1', '2'),     ('1', '2', '2', '1'),     ('2', '1', '1', '2'),     ('2', '1', '2', '1'),     ('2', '2', '1', '1')}            l2 = '1234'        perm(l2)    {('1', '2', '3', '4'),     ('1', '2', '4', '3'),     ('1', '3', '2', '4'),     ('1', '3', '4', '2'),     ('1', '4', '2', '3'),     ('1', '4', '3', '2'),     ('2', '1', '3', '4'),     ('2', '1', '4', '3'),     ('2', '3', '1', '4'),     ('2', '3', '4', '1'),     ('2', '4', '1', '3'),     ('2', '4', '3', '1'),     ('3', '1', '2', '4'),     ('3', '1', '4', '2'),     ('3', '2', '1', '4'),     ('3', '2', '4', '1'),     ('3', '4', '1', '2'),     ('3', '4', '2', '1'),     ('4', '1', '2', '3'),     ('4', '1', '3', '2'),     ('4', '2', '1', '3'),     ('4', '2', '3', '1'),     ('4', '3', '1', '2'),     ('4', '3', '2', '1')}