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

• ovgolovin: Is it OK that reverse is used on each iteration? It has O(n) complexity, and the fact it's run on every iteration may make the whole algorithm pretty slow.
• ovgolovin: I modified the code a bit for it to be more to the point and reflect the names used to describe the algorithm in the Knuth's book. For those who need it I post the link: ideone.com/juG94
• ovgolovin: Also, I have rewritten this algorithm using more functional style coding (with generators). It's a few times slower than the version working directly with indexes. Still, the main part of the algorithm (beginning with while True:) looks more clear in this version. The code is here: ideone.com/mvu1y
• freude: Nice work, but I can not realize why it does not work with zeros in the sequence
• nneonneo: @freude: this function iterates until it reaches the largest lexicographical permutation, then stops. Therefore, to obtain all permutations, make sure to sort your input (so that it is the lowest permutation, lexicographically).

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

• nivniv: undoubtedly the neatest answer

Answer 3

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

• Leland Hepworth: The following is sufficient and concise: set(permutations(s))
• LetzerWille: @LelandHepworth, Yes, you are correct. There was no need for using re or list.

Answer 4

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

Answer 5

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

Answer 6

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.