# Generate permutations of list with repeated elements

Each Answer to this Q is separated by one/two green lines.

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

## 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
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.

The answers/resolutions are collected from stackoverflow, are licensed under cc by-sa 2.5 , cc by-sa 3.0 and cc by-sa 4.0 .