Generar permutaciones de lista con elementos repetidos

Question

En Python, es bastante simple producir todas las permutaciones de una lista usando el módulo itertools. Tengo una situación en la que la lista que estoy usando solo tiene dos caracteres (es decir, '1122'). Quiero generar todas las permutaciones únicas.

Para la cadena '1122', hay 6 permutaciones únicas (1122, 1212, 1221, etc.), pero itertools.permutations producirá 24 elementos. Es simple registrar solamente las permutaciones únicas, pero tomará mucho más tiempo del necesario recogerlas ya que se consideran los 720 artículos.

¿Existe una función o módulo que tenga en cuenta los elementos repetidos al generar permutaciones para que no tenga que escribir el mío?

Answer 1

This web page parece prometedor.

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

Siete años más tarde, aquí es un mejor algoritmo (mejor para mayor claridad):

from itertools import permutations 

def unique_perms(series): 
    return {"".join(p) for p in permutations(series)} 

print(sorted(unique_perms('1122')))