Générer des permutations de liste avec des éléments répétés

Question

En Python, il est assez simple de produire toutes les permutations d'une liste en utilisant le module itertools. J'ai une situation où la liste que j'utilise n'a que deux caractères (c'est-à-dire '1122'). Je veux générer toutes les permutations uniques.

Pour la chaîne '1122', il y a 6 permutations uniques (1122, 1212, 1221, etc.), mais itertools.permutations donnera 24 items. Il est simple de n'enregistrer que les permutations uniques, mais cela prendra beaucoup plus de temps que nécessaire pour les collecter puisque les 720 éléments sont considérés.

Existe-t-il une fonction ou un module qui prend en compte les éléments répétés lors de la génération de permutations afin de ne pas avoir à écrire les miens?

Answer 1

This web page semble prometteur.

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

Sept ans plus tard, voici un meilleur algorithme (mieux pour plus de clarté):

from itertools import permutations 

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

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