Outils pour utilisateurs

Outils du site


permutations

Permutations

Objectif

Exemple: soit une liste d'objets [1,2,3]:

  • on veut savoir les présenter de toutes les façons possibles: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]],
  • en tenant compte si nécessaire des répétitions (ex: [1,2,2]
  • et on veut savoir combien il y en a.


Référence externe pour la définition: voir http://fr.wikipedia.org/wiki/Permutation

Calcul du nombre de permutations

Nombre de permutations sans répétition

Dans l'exemple ci-dessus, il y a 6 permutations de ces 3 objets, et ce nombre de permutations se calcule simplement: il est égal à factorielle 3 = 6.

On va donc reprendre le code de la factorielle dans sa version non récursive:

def permut(n):
    """Calcule le nombre de permutations de n objets (n: entier >= 0)"""
    x = 1
    for i in xrange(2, n+1):
        x *= i
    return x

Exemple d'utilisation:

print permut(3)
6

Nombre de permutations avec répétition

Là, on a un objet plus complexe, composés d'éléments dont certains peuvent se répéter.

Par exemple: [1,2,2,3,4,5,5,5]. Il y a 8 objets, mais le 2 est mis 2 fois et le 5 est mis 3 fois.

Ainsi, il y aura permut(8)=40320 façons de présenter cette liste, mais certaines seront identiques!

On veut donc calculer ici le nombre de permutations en ne comptant qu'une seule fois les permutations identiques.

Il suffit de diviser le nombre total de permutations par chacune des factorielles des répétitions.

Pour reprendre l'exemple: permut(8)//(fact(2)*fact(3)) = 3360

Voilà le code qui fait ça. Pour le lancer, on met comme paramètre le nombre d'objet à permuter, suivi éventuellement de la liste des répétitions:

def permut(n, r=[]):
    """Calcule le nombre de permutations avec ou sans répétition de n objets
       r est la liste des éventuelles répétitions rencontrées dans les n objets
       exemple: [1,2,2,3,4,5,5,5] => permut(8,[2,3]) 
    """
    x = 1
    for i in xrange(2, n+1):
        x *= i
    for m in r:
        y = 1
        for i in xrange(2, m+1):
            y *= i
        x //= y
    return x

Exemple:

# objet de 8 éléments avec le 2 mis 2 fois et le 5 mis 3 fois
seq = [1,2,2,3,4,5,5,5]
 
# nombre total de permutation sans répétition
print permut(len(seq))
40320
 
# nombre de permutations avec répétitions
# (= en ne comptant qu'une seule fois les permutations identiques)
print permut(len(seq), [2, 3])
3360

Bien entendu, on peut calculer automatiquement la liste des répétitions des objets dans la liste des objets.

Par exemple comme suit (code très auto-commenté!):

def repetelem(seq):
    """Donne la liste des répétitions > 1 des éléments dans la séquence seq"""
    r = [] # pour enregistrer les éléments déjà traités
    d = [] # pour enregistrer le nombre de répétitions > 1 des éléments
    for elem in seq:
        if (elem not in r): # si l'élément n'a pas encore été rencontré
            r.append(elem)  # on l'enregistre
            x = seq.count(elem)  # on compte le nb de fois qu'il existe dans seq
            if x>1:  # s'il existe en plusieurs exemplaires
                d.append(x)  # on enregistre le nombre de ses répétitions
    return d  # on renvoie la liste des répétitions > 1 rencontrées

Exemple d'utilisation:

seq = [1,2,2,3,4,4,4,5,6,6,6,6,6,6]
 
print repetelem(seq)
[2, 3, 6]
 
print permut(len(seq))
87178291200 
 
print permut(len(seq), repetelem(seq))
10090080

S'il n'y a qu'une seule de ces 2 fonctions permut() à retenir (sans ou avec répétition), c'est bien celle avec répétition, parce qu'elle fait tout:

  • s'il n'y a qu'un seul argument, c'est qu'on n'a pas de répétition (ou qu'on n'en tient pas compte).
  • dans le cas contraire, il suffit d'ajouter la liste des répétitions.

Liste des permutations de chaînes de caractères présentées dans une liste

On sait maintenant calculer le nombre de permutations, mais on voudrait maintenant connaitre la liste des permutations elle-même.

Par exemple: trouver toutes les permutations possibles de [1, 2, 3], c'est à dire: [1, 2, 3], [1, 3, 2], [2, 3, 1], [2, 1, 3], [3, 1, 2], [3, 2, 1]

Ça pourrait, bien sûr, être une liste de n'importe quoi: ['truc','machin','bidule'].

Sont présentés ci-dessous un code non-récursif (que je conseille) et un code récursif. Ils sont basés sur le même principe: des rotations des éléments qui se trouvent entre l'indice k et la fin de liste.

Par exemple pour seq=[1,2,3,4]:

  • pour k=0, on aura les rotations: [1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]
  • pour k=1, on aura les rotations: [1,2,3,4], [1,3,4,2], [1,4,2,3]
  • pour k=2, on aura les rotations: [1,2,3,4], [1,2,4,3]
  • pour k=3, c'est à dire pour k=len(seq)-1, on n'a plus d'autre rotation que [1,2,3,4]

Pour chaque k, il y a len(seq)-k rotations en tout (c'est à dire len(seq)-k-1 en plus du seq initial)

Pour faire une rotation à partir de l'indice k, vous voyez comment on fait: z.append(z.pop(k)) retire l'élément d'indice k et le remet à la fin de la liste.


Bon. Dans vos essais, soyez raisonnables: n'oubliez pas que le nombre de permutation augmente très rapidement avec la longueur de la liste seq (factorielle de len(seq)). Ainsi, une liste toute simple comme seq = [1,2,3,4,5,6,7,8,9] donnera (en moins d'une seconde avec le code non-récursif) la liste des 362880 façons de présenter la liste seq. Cette liste sera tellement longue qu'elle risque même de ne pas pouvoir s'afficher sur votre PC…

Code non récursif

Le code non-récursif est ici assez concis et très rapide (2 à 3 fois plus que le code récursif).

Voilà le code:

def permutliste(seq, er=False):
    """Retourne la liste de toutes les permutations de la liste seq (non récursif).
       si er=True: élimination des répétitions quand seq en a (ex: [1,2,2]
    """
    p = [seq]
    n = len(seq)
    for k in xrange(0,n-1):
        for i in xrange(0, len(p)):
            z = p[i][:]
            for c in xrange(0,n-k-1):
                z.append(z.pop(k))
                if er==False or (z not in p):
                    p.append(z[:])
    return p

On peut améliorer sa présentation avec un tri (avec p.sort() ou sorted(p) par ex.).

On a tenu compte d'un 2ème argument ici pour éviter les répétitions. En effet, quand la liste initiale seq contient des éléments qui se répètent, le résultat contiendra plusieurs listes identiques. Pour que ces listes identiques ne soient comptées qu'une seule fois, il suffit d'ajouter True comme 2ème argument au lancement de la fonction.

Exemple d'utilisation:

seq = [1,2,3]
print permutliste(seq)
[[1, 2, 3], [1, 3, 2], [2, 3, 1], [2, 1, 3], [3, 1, 2], [3, 2, 1]]
 
seq = [1,2,2]
print permutliste(seq)
[[1, 2, 2], [2, 2, 1], [2, 1, 2], [1, 2, 2], [2, 1, 2], [2, 2, 1]]
 
seq = [1,2,2]
print permutliste(seq, True)
[[1, 2, 2], [2, 2, 1], [2, 1, 2]]

Code récursif

Voilà le code récursif:

def permutliste(seq, er=False, k=0):
    """retourne la liste de toutes les permutations de la liste seq (récursif)
       si er=True: élimination des répétitions quand seq en a (ex: [1,2,2]
    """
    n = len(seq)
    if k == n-1:
        return []
    p = []
    z = seq[:]
    for c in xrange(0, n-k):
        if er==False or (z not in p):
            p.append(z[:])
            p.extend(permutliste(z, er, k+1)[1:])
        z.append(z.pop(k))
    return p

On ne donne jamais le 3ème argument k qui n'est utilisé que comme variable interne.

Au lancement de la fonction permutliste([1,2,3,4]), le 1er passage (sans la récursion), donnera avec k=0 les 4 rotations: [1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]. Pour chacune de ces valeurs, un appel récursif avec l'indice de rotation k+1 permettra de retourner toutes les séquences de rotation suivantes. Etc… jusqu'à ce que k=len(seq)-1 auquel cas il n'y a plus de rotation à faire.

Ce code donne bien entendu les mêmes résultats que le code non-récursif.

Si vous voulez un résultat plus “présentable”, vous pouvez trier la liste résultat (ex: r.sort() ou sorted(r)).

Et pour éviter les répétitions au cas où des éléments se répètent dans la liste seq, on ajoute simplement l'argument True comme pour le code non-récursif.

Liste des permutations des caractères d'une chaîne de caractères

Même principe que précédemment, à part qu'on cherche les permutations des caractères dans une chaîne. Par exemple, 'ABC' ⇒ ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']

Utilisation possible (entre autres): recherche d'anagrammes (voir http://fr.wikipedia.org/wiki/Anagramme)

La solution de codage utilise l'une des fonctions précédentes qui traite les listes (Python est vraiment doué pour manipuler des listes!):

def permutchaine(ch, er=False):
    """retourne la liste de toutes les permutations des caractères de la chaine ch
       avec er=True pour éviter les répétitions quand ch en a (ex: 'abb')
    """
    return [''.join(z) for z in permutliste(list(ch), er)]
# exemples d'utilisation:
print permutchaine("ABC")  # affiche ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']

Si vous voulez que la chaîne résultat soit rangée selon l'ordre alphabétique, ou même dans l'ordre alphabétique inverse:

R=permutchaine("CBA")
print R  # affiche: ['BCA', 'BAC', 'ABC', 'ACB', 'CAB', 'CBA']
R.sort()
print R  # affiche: ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']
R.reverse()
print R  # affiche: ['CBA', 'CAB', 'BCA', 'BAC', 'ACB', 'ABC']

Il y a une utilisation très intéressante de permutchaine(): calculer toutes les permutations sans répétition d'une chaîne de bits:

Par exemple:

print sorted(permutchaine('1100', True),reverse=True)

Ce qui affichera (en une seule ligne):

[
'1100', 
'1010', 
'1001', 
'0110', 
'0101', 
'0011'
]


Amusez-vous bien!

permutations.txt · Dernière modification: 2010/01/09 11:27 par tyrtamos

Outils de la page