Pourquoi les itertools.permutations de Python contiennent-ils des doublons? (Quand la liste originale a des doublons)

Question

Il est universellement reconnu qu'une liste de n distincts symboles a n! permutations. Cependant, quand les symboles ne sont pas distincts, le plus commun de la convention, en mathématiques et ailleurs, semble être pour compter uniquement les permutations distinctes. Ainsi, les permutations de la liste [1, 1, 2] sont généralement considérés comme des
[1, 1, 2], [1, 2, 1], [2, 1, 1]. En effet, le code C++ suivant imprime précisément ces trois là:

int a[] = {1, 1, 2};
do {
    cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
} while(next_permutation(a,a+3));

Sur l'autre main, Python itertools.permutations semble impression de quelque chose d'autre:

import itertools
for a in itertools.permutations([1, 1, 2]):
    print a

Cette affiche

(1, 1, 2)
(1, 2, 1)
(1, 1, 2)
(1, 2, 1)
(2, 1, 1)
(2, 1, 1)

En tant qu'utilisateur Artsiom Rudzenka souligné en réponse à une question, la documentation Python dit:

Les éléments sont traités comme unique fonction de leur position, et non sur leur valeur.

Ma question: pourquoi cette conception de décision?

Il semble qu'à la suite de la convention habituelle, donnerait des résultats qui sont plus utiles (et en effet, il est généralement exactement ce que je veux)... ou est-il une application de Python est un comportement que je suis absent?

[Ou est-ce un problème de mise en œuvre? L'algorithme que dans next_permutation - par exemple expliqué sur StackOverflow ici (par moi) et illustré ici à O(1) amorti - semble efficace et applicable en Python, mais est Python faire quelque chose d'encore plus efficace car il ne garantit pas l'ordre lexicographique, fondée sur des valeurs? Et si oui, l'augmentation de l'efficacité considéré en vaut la peine?]

Answer 1

Je ne peux pas parler pour le concepteur de l' itertools.permutations (Raymond Hettinger), mais il me semble qu'il y a un couple de points en faveur de la conception:

Tout d'abord, si vous avez utilisé un next_permutation-approche de style, alors vous seriez limité de passage dans les objets qui prennent en charge un linéaire de la commande. Alors qu' itertools.permutations fournit des permutations de tout type d'objet. Imaginez combien ennuyeux ce serait:

>>> list(itertools.permutations([1+2j, 1-2j, 2+j, 2-j]))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: no ordering relation is defined for complex numbers

Deuxièmement, par pas de test pour l'égalité sur les objets, itertools.permutations évite de payer le coût de l'appel de la __eq__ méthode dans le cas habituel où il n'est pas nécessaire.

Fondamentalement, itertools.permutations résout la plupart des cas de manière fiable et à moindre coût. Il y a certainement un argument qu' itertools doivent fournir une fonction qui évite de dupliquer les permutations, mais une telle fonction devrait être de plus de itertools.permutations, et non à la place il. Pourquoi ne pas écrire une telle fonction et de soumettre un patch?

Answer 2

Je suis d'accepter la réponse de Gareth Rees est la plus attrayante explication (à court d'une réponse de la bibliothèque Python designers), à savoir que Python itertools.permutations on ne peut pas comparer les valeurs des éléments. Venez pour penser à elle, c'est ce que la question demande, mais je vois maintenant comment il pourrait être vu comme un avantage, en fonction de ce que l'on utilise habituellement itertools.permutations pour.

Juste pour être complet, j'ai comparé trois méthodes pour générer un ensemble distinct de permutations. La méthode 1, ce qui est très inefficace de la mémoire et de temps de sages, mais qui nécessite le moins nouveau code, consiste à envelopper Python itertools.permutations, comme dans zeekay de réponse. Méthode 2 est un générateur basé sur la version de C++ next_permutation, de cet article de blog. La méthode 3 est quelque chose que j'ai écrit qui est encore plus proche de C++ next_permutation algorithme; il modifie la liste en place (je n'ai pas fait trop général).

def next_permutationS(l):
    n = len(l)
    #Step 1: Find tail
    last = n-1 #tail is from `last` to end
    while last>0:
        if l[last-1] < l[last]: break
        last -= 1
    #Step 2: Increase the number just before tail
    if last>0:
        small = l[last-1]
        big = n-1
        while l[big] <= small: big -= 1
        l[last-1], l[big] = l[big], small
    #Step 3: Reverse tail
    i = last
    j = n-1
    while i < j:
        l[i], l[j] = l[j], l[i]
        i += 1
        j -= 1
    return last>0

Voici quelques résultats. J'ai encore plus de respect pour Python fonction intégrée maintenant: c'est trois à quatre fois plus rapide que les autres méthodes lorsque les éléments sont tous (ou presque tous) distinctes. Bien sûr, quand il ya beaucoup d'éléments répétés, il est une idée terrible.

Some results ("us" means microseconds):

l                                       m_itertoolsp  m_nextperm_b  m_nextperm_s
[1, 1, 2]                               5.98 us       12.3 us       7.54 us
[1, 2, 3, 4, 5, 6]                      0.63 ms       2.69 ms       1.77 ms
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]         6.93 s        13.68 s       8.75 s

[1, 2, 3, 4, 6, 6, 6]                   3.12 ms       3.34 ms       2.19 ms
[1, 2, 2, 2, 2, 3, 3, 3, 3, 3]          2400 ms       5.87 ms       3.63 ms
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2]          2320000 us    89.9 us       51.5 us
[1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4]    429000 ms     361 ms        228 ms

Le code est ici si quelqu'un veut explorer.

Answer 3

Il est assez facile d'obtenir le comportement que vous préférez en les enveloppant itertools.permutations, ce qui pourrait avoir influencé la décision. Comme décrit dans la documentation, itertools est conçu comme un ensemble de blocs de construction/des outils à utiliser dans la construction de votre propre itérateurs.

def unique(iterable):
    seen = set()
    for x in iterable:
        if x in seen:
            continue
        seen.add(x)
        yield x

for a in unique(permutations([1, 1, 2])):
    print a

(1, 1, 2)
(1, 2, 1)
(2, 1, 1)

Cependant, comme souligné dans les commentaires, cela pourrait ne pas être aussi efficace que vous le souhaitez:

>>> %timeit iterate(permutations([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]))
1 loops, best of 3: 4.27 s per loop

>>> %timeit iterate(unique(permutations([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2])))
1 loops, best of 3: 13.2 s per loop

Peut-être que si il ya suffisamment d'intérêt, une nouvelle fonction ou d'un argument optionnel pour itertools.permutations pourrait être ajouté à l' itertools, pour générer des permutations sans doublons de manière plus efficace.

Answer 4

Je trouve aussi surprenant que itertools n'ont pas de fonction pour la plus intuitive de la notion de unique de permutations. Générer répétitif permutations seulement à sélectionner les uniques d'entre eux est hors de question pour toute application sérieuse.

J'ai écrit mon propre itératif générateur de fonction qui se comporte de façon similaire à l' itertools.permutations mais ne retourne pas les doublons. Seuls les permutations de la liste d'origine sont considérés comme, des sous-listes peuvent être créées avec la norme itertools bibliothèque.

def unique_permutations(t):
    lt = list(t)
    lnt = len(lt)
    if lnt == 1:
        yield lt
    st = set(t)
    for d in st:
        lt.remove(d)
        for perm in unique_permutations(lt):
            yield [d]+perm
        lt.append(d)

Answer 5

Peut-être que je me trompe, mais il semble que la raison de cela est dans "les Éléments sont traités comme unique fonction de leur position, et non sur leur valeur. Donc, si les éléments d'entrée sont uniques, il n'y aura aucune répétition des valeurs dans chaque permutation.' Vous avez spécifié (1,1,2) et à partir de votre point de vue 1 à l'indice 0 et de 1 au 1 de l'indice sont les mêmes - mais ce n'est pas ainsi, depuis les permutations python de mise en œuvre utilisés index au lieu de valeurs.

Donc, si nous prenons un coup d'oeil à la valeur par défaut de python permutations de mise en œuvre, nous allons voir qu'il utilise les index:

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)

Par exemple, si vous changez d'entrée pour [1,2,3], vous obtiendrez de corriger les permutations([(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]) puisque les valeurs sont uniques.