Generate permutations of list with repeated elements

In Python, it is quite simple to produce all permutations of a list using the itertools module. I have a situation w开发者_JS百科here 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')))

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

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

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

from more_itertools import distinct_permutations

x = [p for p in distinct_permutations(['M','I','S', 'S', 'I'])]

for item in x:
    
  print(item)

Output:

('I', 'S', 'S', 'I', 'M')
('S', 'I', 'S', 'I', 'M')
('S', 'S', 'I', 'I', 'M')
('I', 'S', 'I', 'S', 'M')
('S', 'I', 'I', 'S', 'M')
('I', 'I', 'S', 'S', 'M')
('I', 'S', 'I', 'M', 'S')
('S', 'I', 'I', 'M', 'S')
('I', 'I', 'S', 'M', 'S')
('I', 'I', 'M', 'S', 'S')
('I', 'S', 'S', 'M', 'I')
('S', 'I', 'S', 'M', 'I')
('S', 'S', 'I', 'M', 'I')
('S', 'S', 'M', 'I', 'I')
('I', 'S', 'M', 'S', 'I')
('S', 'I', 'M', 'S', 'I')
('S', 'M', 'I', 'S', 'I')
('S', 'M', 'S', 'I', 'I')
('I', 'M', 'S', 'S', 'I')
('M', 'I', 'S', 'S', 'I')
('M', 'S', 'I', 'S', 'I')
('M', 'S', 'S', 'I', 'I')
('I', 'S', 'M', 'I', 'S')
('S', 'I', 'M', 'I', 'S')
('S', 'M', 'I', 'I', 'S')
('I', 'M', 'S', 'I', 'S')
('M', 'I', 'S', 'I', 'S')
('M', 'S', 'I', 'I', 'S')
('I', 'M', 'I', 'S', 'S')
('M', 'I', 'I', 'S', 'S')

A very simple solution, likely similar to what is used by more_itertools, which takes advantage of the lexicographical order of permutations as suggested by @Brayoni, can be done by building an index of the iterable.

Let's say you have L = '1122'. You can build a very simple index with something like this:

index = {x: i for i, x in enumerate(sorted(L))}

Let's say you have a permutation P of L. It does not matter how many elements P has. Lexicographical ordering dictates that if you map P to using the index, it must always increase. Map P like this:

mapped = tuple(index[e] for e in p)  # or tuple(map(index.__getitem__, p))

Now you can discard elements that are less than or equal to the maximum seen so far:

def perm_with_dupes(it, n=None):
    it = tuple(it)   # permutations will do this anyway
    if n is None:
        n = len(it)
    index = {x: i for i, x in enumerate(it)}
    maximum = (-1,) * (len(it) if n is None else n)
    for perm in permutations(it, n):
        key = tuple(index[e] for e in perm)
        if key <= maximum: continue
        maximum = key
        yield perm

Notice that there is no additional memory overhead past keeping the last maximum item around. You can join the tuples with '' if you like.