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 permutations

def 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 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

This is also a common interview question. In the event standard library modules can't be used, here is an implementation to consider:

We define a lexicographic ordering of permutations. Once we do that we can just start with the smallest permutation and increment it minimally till we reach the largest permutation.

def next_permutation_helper(perm):
    if not perm:
        return perm

    n = len(perm)

    """
    Find k such that p[k] < p[k + l] and entries after index k appear in
    decreasing order.
    """
    for i in range(n - 1, -1, -1):
        if not perm[i - 1] >= perm[i]:
            break

    # k refers to the inversion point
    k = i - 1

    # Permutation is already the max it can be
    if k == -1:
        return []

    """
    Find the smallest p[l] such that p[l] > p[k]
    (such an l must exist since p[k] < p[k + 1].
    Swap p[l] and p[k]
    """
    for i in range(n - 1, k, -1):
        if not perm[k] >= perm[i]:
            perm[i], perm[k] = perm[k], perm[i]
            break

    # Reverse the sequence after position k.
    perm[k + 1 :] = reversed(perm[k + 1 :])

    return perm


def multiset_permutation(A):
    """
    We sort array first and `next_permutation()` will ensure we generate
    permutations in lexicographic order
    """
    A = sorted(A)
    result = list()

    while True:
        result.append(A.copy())
        A = next_permutation_helper(A)
        if not A:
            break

    return result

Output:

>>> multiset_permutation([1, 1, 2, 2])
[[1, 1, 2, 2], [1, 2, 1, 2], [1, 2, 2, 1], [2, 1, 1, 2], [2, 1, 2, 1], [2, 2, 1, 1]]

You can transform the output from the mutable list to string using join on this line:

result.append("".join(map(str, A.copy())))

to get:

['1122', '1212', '1221', '2112', '2121', '2211']

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

from itertools import permutations

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