Différences

Ci-dessous, les différences entre deux révisions de la page.

--- combinatoire [2009/12/29 10:15]
tyrtamos
+++ combinatoire [2010/01/09 09:18]
tyrtamos
@@ Ligne 1: / Ligne 1: @@
-====== Analyse combinatoire ======
+====== Généralités sur l'analyse combinatoire ======
 **En cours de modification! (20/12/2009)**
-===== Permutations =====
+La page relative à l'analyse combinatoire commençant à être trop grande, elle a été découpée en quatre pages: permutations, ensemble des parties d'un ensemble, combinaisons et arrangements.
-Référence pour la définition: voir [[http://fr.wikipedia.org/wiki/Permutation]]
-Par exemple, les permutations de trois objets distincts A, B et C sont: ABC, ACB, BAC, BCA, CAB, CBA.
-==== 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:
-<code python>
+===== Permutations =====
-def permut(n):
-    """Calcule le nombre de permutations de n objets (n: entier >= 0)"""
-    x = 1
-    for i in xrange(2, n[0]+1):
-        x *= i
-    return x
-</code>
-Exemple d'utilisation:
+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]]%%, et on veut savoir combien il y en a.
-<code python>
+Référence externe pour la définition: voir [[http://fr.wikipedia.org/wiki/Permutation]]
-print permut(3)
-</code>
-=== 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:
-<code python>
-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
-</code>
-Exemple:
-<code python>
-# 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))
-# nombre de permutations avec répétitions
-# (= en ne comptant qu'une seule fois les permutations identiques)
-print permut(len(seq), [2, 3])
-</code>
-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é!):
-<code python>
-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
-</code>
-Exemple d'utilisation:
-<code python>
-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
-</code>
-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...
-=== 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:
-<code python>
-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
-</code>
-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:
-<code python>
-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>
-=== Code récursif ===
-Voilà le code récursif:
-<code python>
-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
-</code>
-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!):
-<code python>
-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)]
-</code>
-<code python>
-# exemples d'utilisation:
-print permutchaine("ABC")  # affiche ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']
-</code>
-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:
-<code python>
-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']
-</code>
-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:
-<code python>
-print sorted(permutchaine('1100', True),reverse=True)
-</code>
-Ce qui affichera (en une seule ligne):
-<code python>[
-'1100',
-'1010',
-'1001',
-'0110',
-'0101',
-'0011'
-]</code>
+Page du site qui traite des permutations: [[http://python.jpvweb.com/mesrecettespython/permutations]]
 ===== Ensemble des parties d'un ensemble =====
-Il s'agit ici de tous les sous-ensembles qu'on peut construire à partir d'un ensemble d'objets.
-Par exemple: [1,2,3]  =>  [], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]
-Pour la théorie, voir ici (entre autres): [[http://fr.wikipedia.org/wiki/Ensemble_des_parties_d%27un_ensemble]]
-==== Nombre des parties d'un ensemble ====
-Combien il en a? => si l'ensemble possède n objets, on peut constituer %%2**n%% sous-ensembles.
-<code python>
-def parties(n):
-    return 2**n
-</code>
-En fait, on verra après (chapitre sur les combinaisons) qu'on peut le retrouver d'une autre façon: le nombre total de sous-ensemble est égal à la somme des combinaisons:
-<m>sum{k=0}{n}{C^k_n}</m>
-Essayons avec un ensemble de 3 éléments:
-  * Combinaison de 3 objets pris de 0 à 0 => 1  ([])
-  * Combinaison de 3 objets pris de 1 à 1 => 3  ([1], [2], [3])
-  * Combinaison de 3 objets pris de 2 à 2 => 3  ([1, 2], [1, 3], [2, 3])
-  * Combinaison de 3 objets pris de 3 à 3 => 1  ([1, 2, 3])
-Total = 8 = %%2**3%%
-==== Liste des parties d'un ensemble composé d'une liste ====
-On voudrait maintenant construire automatiquement une telle liste dans le cas général. Comment on fait?
-Pour résoudre ce genre de problème, il y a une solution que j'aime bien, qui n'est pas trop complexe à comprendre et qui n'est pas récursive: il s'agit de s'appuyer sur le comptage en binaire.
-Avec une liste composée de n éléments, on va compter de 0 à %%2**n-1%%, et pour chaque valeur de ce compteur, on va placer un élément de la liste à chaque 1 qu'on aura dans la représentation binaire du compteur.
-Exemple:
-liste = ['a', 'b', 'c'] donc n=len(liste)=3 éléments
-On va donc compter de 0 à %%2**3-1=7%%
-<code>
-   000   []
-   001   ['c']
-   010   ['b']
-   011   ['b', 'c']
-   100   ['a']
-   101   ['a', 'c']
-   110   ['a', 'b']
-   111   ['a', 'b', 'c']
-</code>
-On voit bien dans cet exemple: pour une valeur du compteur, s'il y a un '1' en 2ème position, alors on ajoute un 'b' dans la liste correspondant à ce compteur.
-Et pour n'avoir que les solutions à 2 éléments, par exemple, il suffit de n'ajouter la solution d'un compteur que si cette solution a exactement 2 éléments. On retrouvera bien entendu ainsi la liste des combinaisons de 3 objets pris 2 à 2.
-Voilà un code qui fait tout cela. l'argument 'seq' est la liste des n objets. La fonction retourne la liste des parties de cet liste.
-<code python>
-def partiesliste(seq):
-    p = []
-    i, imax = 0, 2**len(seq)-1
-    while i <= imax:
-        s = []
-        j, jmax = 0, len(seq)-1
-        while j <= jmax:
-            if (i>>j)&1 == 1:
-                s.append(seq[j])
-            j += 1
-        p.append(s)
-        i += 1
-    return p
-</code>
-Vous voyez comment on teste s'il y a un '1' à la position j dans la représentation binaire de i: par un décalage binaire (opérateur %%'>>'%%) et un 'or' logique (opérateur %%&%%).
-Par exemple: i=8 => '00001000'. Pour savoir s'il y a un '1' à la position j=3 (compté de droite à gauche à partir de 0), on fera: %%(i>>j)&1==1%% qui ici donnera True.
-Exemple d'utilisation:
-<code python>
-seq = [1,2,3]
-print partiesliste(seq)
-[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
-</code>
-On se servira de ce code légèrement modifié pour calculer la liste des combinaisons, puisqu'il suffit d'extraire de la liste des parties toutes les listes ayant le nombre voulu d'éléments.
-==== Liste des parties d'un ensemble composé d'une chaine de caractères ====
-On a ici une chaine de caractère, et on veut obtenir la liste de toutes les parties de l'ensemble formé par cette chaine.
-Par exemple: %%"ABC" => ['', 'A', 'B', 'AB', 'C', 'AC', 'BC', 'ABC']%%
-On va utiliser la fonction qui traite les listes:
-<code python>
-def partieschaine(ch):
-    """Retourne la liste de toutes les parties de l'ensemble des caractères de la chaine ch"""
-    return [''.join(z) for z in partiesliste(list(ch))]
-</code>
-Exemple d'utilisation:
-<code python>
-print partieschaine("ABC")
-['', 'A', 'B', 'AB', 'C', 'AC', 'BC', 'ABC']
-</code>
 ===== Combinaisons =====
-Voir pour la définition (entre autres): [[http://fr.wikipedia.org/wiki/Combinaison_%28math%C3%A9matiques%29]]
-Par exemple, on cherche les combinaisons de 3 objets pris 2 à 2: %%['A','B','C']%% => %%[['A', 'B'], ['A', 'C'], ['B', 'C']]%%
-Contrairement aux permutations, on ne tient pas compte de l'ordre: ainsi, ['A','B'] et ['B','A'] ne compte que pour 1.
-==== Nombre de combinaisons de n objets pris k à k ====
-Le calcul du nombre de combinaisons de n objets pris k à k est donnée par la formule:
-<m>Cnk~=~{n!}/{k!(n-k)!}~=~{n(n-1)(n-2)...(n-k+1)}/{k!}</m>
-Soit, en Python (si fact(n)=factorielle de n):
-Cnk = fact(n)/(fact(k)*fact(n-k)) = n*(n-1)*(n-2)*...*(n-k+1)/fact(k)
-=== Solution non-récursive ===
-Puisque nous sommes sous Python qui sait calculer des nombres entiers énormes, nous pouvons utiliser brutalement les factorielles en prenant la fonction fact(n) présentée ailleurs sur ce site:
-<code python>
-combin = lambda n,k: fact(n)//(fact(k)*fact(n-k))
-</code>
-Il est difficile de faire plus simple...
-Mais le plus efficace est quand même le suivant, qui calcule progressivement le résultat sans calculer des grands nombres:
-<code python>
-def combin(n, k):
-    """Nombre de combinaisons de n objets pris k a k"""
-    if k > n//2:
-        k = n-k
-    x = 1
-    y = 1
-    i = n-k+1
-    while i <= n:
-        x = (x*i)//y
-        y += 1
-        i += 1
-    return x
-</code>
-Attention à ne pas utiliser dans ce code le raccourci habituel %%x *= i//y%%, car il faut que la multiplication ait lieu **avant** la division entière, sinon celle-ci ne tombe pas juste, et le résultat final est faux.
-Pour que cette fonction soit utilisable avec de très grands nombres, j'ai tenu compte des points suivants:
-  * il faut utiliser while au lieu de for, car xrange() ne supporte pas les types 'long' (en contrepartie de sa rapidité).
-  * si %%k>n//2%%, alors combin(n,k) est remplacé par combin(n, n-k) qui donne le même résultat avec moins de calculs.
-Exemple d'utilisation:
-<code python>
-print combin(3,2)  # affiche 3
-print combin(50,20)  # affiche 47129212243960
-</code>
-Ce code est très rapide: par exemple, le nombre de combinaisons de 100000 (cent mille) objets pris 100 à 100 donne en moins d'1/1000 de seconde un nombre de 343 chiffres:
-<code>
-1019745118068508355816143175813864936340849501519143871777101229221311704707028464150801159851819171048218667041957300317610197834902713500555020173048960798706784754817501032954266210951200883251987669862675631847360156537041811409331039637713779759572781307343494274990819880664139309679429703675390591419799883108282575404188096902252124000
-</code>
-=== Solution récursive ===
-La solution récursive est particulièrement simple:
-<code python>
-def combin(n,k):
-    """Nombre de combinaisons de n objets pris k a k (calcul récursif)"""
-    if k==0 or k==n:
-        return 1
-    return combin(n-1, k-1) + combin(n-1,k)
-</code>
-Malheureusement, cette solution est moins rapide que la dernière solution étudiée. De plus, elle est limitée à cause de la taille de la pile de récursion (env. 1000).
-Pour mémoire, citons une version non-récursive qui imite assez bien la version récursive en gérant directement la pile des appels:
-<code python>
-def combin(n, k):
-    """Nombre de combinaisons de n objets pris k a k (non récursif, mais imitant le récursif)"""
-    pile = [[n,k]]
-    r = 0
-    while len(pile)>0:
-        i, j = pile.pop(-1)
-        if j==0 or i==j:
-            r += 1
-        else:
-            pile.append([i-1,j-1])
-            pile.append([i-1,j])
-    return r
-</code>
-Le principe n'est pas très compliqué. On utilise une pile pour conserver les combinaisons en attente de résolution, identifiées par de simples couples de type [n,k]. La variable r, initialisée à 0, contiendra le résultat final.
-- initialement, la pile ne contient que le but à attendre: [n,k].
-- A chaque boucle while, on dépile le dernier couple [i,j]. Les 2 seuls couples dont on connait la valeur correspondent à combin(x,0), 1ère colonne du triangle de Pascal, et combin(x,x), diagonale (ou plutôt hypothénuse) du même triangle, et cette valeur est 1. Dans ce cas, on incrémente r de cette valeur et on continue. Dans les autres cas, on remplace le couple [i,j] par les 2 couples [i-1,j-1] et [i-1,j] qu'on empile.
-La boucle s'arrête quand la pile est vide! et le résultat r est renvoyé.
-Voyons cela sur un exemple. On ajoute juste après le while la ligne suivante (avec la bonne indentation):
-<code python>
-print r, pile
-</code>
-et on lance l'exemple:
-<code python>
-print combin(5,3)
-</code>
-Ce qui affiche:
-<code>
-[[5, 3]]
-[[4, 2], [4, 3]]
-[[4, 2], [3, 2], [3, 3]]
-[[4, 2], [3, 2]]
-[[4, 2], [2, 1], [2, 2]]
-[[4, 2], [2, 1]]
-[[4, 2], [1, 0], [1, 1]]
-[[4, 2], [1, 0]]
-[[4, 2]]
-[[3, 1], [3, 2]]
-[[3, 1], [2, 1], [2, 2]]
-[[3, 1], [2, 1]]
-[[3, 1], [1, 0], [1, 1]]
-[[3, 1], [1, 0]]
-[[3, 1]]
-[[2, 0], [2, 1]]
-[[2, 0], [1, 0], [1, 1]]
-[[2, 0], [1, 0]]
-[[2, 0]]
-</code>
-On voit bien que r n'est incrémentée (et la pile dépilée) que lorsque la combinaison finale est [0,x] ou [x,x].
-Le résultat final est ok, mais par rapport au code non-récursif précédent, celui-ci donne une lenteur... affligeante!
-A ne conserver que pour des considérations théoriques.
-==== Liste des combinaisons d'une liste de n objets pris k à k ====
-Par exemple, nous voulons trouver la liste de toutes les combinaisons de de 3 objets pris 2 à 2, qui est: %%[1,2,3]%% => %%[[1,2], [1,3], [2,3]]%%
-Nous allons reprendre tout simplement le principe de "l'ensemble des parties d'un ensemble" traité plus haut. Mais en limitant notre résultat au nombre k d'éléments voulue dans chaque partie.
-Cela donnera comme code:
-<code python>
-def combinliste(seq, k):
-    p = []
-    i, imax = 0, 2**len(seq)-1
-    while i<=imax:
-        s = []
-        j, jmax = 0, len(seq)-1
-        while j<=jmax:
-            if (i>>j)&1==1:
-                s.append(seq[j])
-            j += 1
-        if len(s)==k:
-            p.append(s)
-        i += 1
-    return p
-</code>
-Exemples d'utilisation:
-<code python>
-print combinliste(['A','B','C'],2) # affiche [['A', 'B'], ['A', 'C'], ['B', 'C']]
-print combinliste(['ab','cd','ef','gh','ij'],3) # affiche [['ab', 'ef', 'ij'], ['ab', 'ef', 'gh'], ['ab', 'gh', 'ij'], ['ab', 'cd', 'gh'], ['ab', 'cd', 'ij'], ['ab', 'cd', 'ef'], ['cd', 'ef', 'gh'], ['cd', 'ef', 'ij'], ['cd', 'gh', 'ij'], ['ef', 'gh', 'ij']]
-</code>
-Comme vu précédemment, ces listes trouvées peuvent être triées.
-==== Liste des combinaisons d'une chaine de n caractères pris k à k ====
-C'est le même principe, à part que la donnée est une chaîne de caractères, et qu'on cherche toutes les combinaisons de k caractères de cette chaîne de longueur n.
-La solution la plus simple est d'utiliser la fonction précédente:
-<code python>
-def combinchaine(ch,k):
-    return [''.join(x) for x in combinliste(list(ch),k)]
-</code>
-Exemple d'utilisation:
-<code python>
-print combinchaine('ABCD',3)
-['ACD', 'ABD', 'ABC', 'BCD']
-</code>
-==== Combinaisons avec répétition ====
-Jusqu'à présent, on a considéré que les objets dont on voulait les combinaisons, étaient tous **distincts**, c'est à dire qu'ils n'apparaissaient qu'une seul fois dans la liste (comme [1,2,3], mais pas comme [1,2,2]. Maintenant, on va voir ce qu'on peut faire avec des répétitions.
-Quand l'un des éléments au moins apparait plusieurs fois dans la liste des objets, il y a deux effets dans la liste des combinaisons.
-Par exemple dans les combinaisons de [1,2,2] pris 2 à 2 qui donne [[1, 2], [1, 2], [2, 2]]:
-  * présence de séquences contenant des répétitions. Ici: [2,2]
-  * présence de séquences identiques. Ici: [1,2] et [1,2].
-Que peut-on faire avec ça? Tout dépendra de ce qu'on obtenir par rapport au problème à résoudre:
-  * on n'a pas de répétition dans la liste des objets de départ mais on en veut dans les résultats
-  * on a des répétitions dans la liste des objets de départ et on veut éliminer ses effets dans les résultats
-Voyons ces 2 cas.
-**__On veut des combinaisons avec répétition__**
-Par exemple: on a [1,2,3], mais on veut obtenir une combinaison de ces 3 objets pris 2 à 2 **avec répétition** comme: %%[[1, 1], [1, 2], [2, 2], [1, 3], [2, 3], [3, 3]]%%
-Il suffit de transformer la liste de départ en répétant chaque élément autant de fois que la combinaison cherchée le demande (ici, 2): [1,2,3] devient donc [1,1,2,2,3,3].
-Combien cela va-t-il donner de séquence dans les résultats? Cela en donnera:
-<m>{C^k_{n+k-1}}</m>
-n étant le nombre d'objets distincts. C'est à dire:
-<code python>
-Combin(3+2-1, 2)
-</code>
-Pour calculer la liste de ces combinaisons avec répétition, on peut utiliser les fonctions sans répétition, et créer une fonction qui répète la liste de départ le nombre de fois voulu:
-<code python>
-def repet(seq, m=-1):
-    """Renvoie un liste avec chaque élément distinct de seq apparait m fois
-       si m==0, renvoie seq sans rien changer
-       si m==-1 (défaut), chaque élément de seq apparait len(seq) fois
-    """
-    if m == 0:
-        return seq[:]
-    if m == -1:
-        m = len(seq)
-    r = []
-    for elem in seq:
-        if elem not in r:
-            for k in xrange(0,m):
-                r.append(elem)
-    return r
-</code>
-Avec cette fonction, la liste d'objet seq=[1,2,3] devient avec seq2=repet(seq,2): [1,1,2,2,3,3]. Et combinliste(seq2,2) donne la liste voulue: %%[[1, 1], [1, 2], [2, 2], [1, 3], [2, 3], [3, 3]]%%.
-On peut faire la même chose avec une chaine de caractère. Par exemple, on veut la liste des mots de 3 lettres de l'alphabet, chaque lettre ne pouvant être répété que 2 fois:
-<code python>
-ch = ''.join(repet(list("abcdefghijklmnopqrstuvwxyz"),2))
-</code>
-===== Arrangement =====
-Référence pour la définition: voir [[http://fr.wikipedia.org/wiki/Arrangement]]
-Par exemple, l'arrangement de 3 objets = ['A','B','C'] pris 2 à 2: %%[['B', 'A'], ['A', 'B'], ['C', 'A'], ['A', 'C'], ['C', 'B'], ['B', 'C']]%%
-Vous voyez la principale différence avec les combinaisons. Pour les combinaisons, ['B', 'A'] et ['A', 'B'] compte pour une seule solution. Autrement dit, les arrangements compteront toutes les permutations de chaque solution trouvée par les combinaisons.
-==== Calcul du nombre d'arrangements ====
-Il y a 6 arrangements, ce qui se compte de la façon suivante:
-<m>Ank~=~{n!}/{(n-k)!}~=~n(n-1)(n-2)...(n-k+1)</m>
-Ou, en Python (si fact(n) est la factorielle de n)
-Ank = fact(n)/fact(n-k) = n*(n-1)*(n-2)*...*(n-k+1)
-Ce qui donne le code suivant:
-<code python>
-def arrang(n, k):
-    """Nombre des arrangements de n objets pris k à k"""
-    if k>n:
-        return 0
-    x = 1
-    i = n-k+1
-    while i <= n:
-        x *= i
-        i += 1
-    return x
-</code>
-Exemple d'utilisation:
-<code python>
-print arrang(5,3)
-
-</code>
-Vous noterez le cas k>n qui est prévu dans la définition mathématique, sans avoir de sens physique (ex: arrangement de 3 objets pris 5 à 5 ???)
-==== Liste des arrangements  d'une liste de n objets pris k à k ====
-Comme nous savons trouver la liste des combinaisons, nous savons trouver la liste des arrangements, puisqu'à chaque combinaison trouvée correspond la liste de toutes les permutations de cette combinaison!
-Par exemple, la liste des combinaisons de 5 objets ['A','B','C','D','E'] pris 3 à 3:
-%%[['A', 'C', 'E'], ['A', 'C', 'D'], ['A', 'D', 'E'], ['A', 'B', 'D'], ['A', 'B', 'E'], ['A', 'B', 'C'], ['B', 'C', 'D'], ['B', 'C', 'E'], ['B', 'D', 'E'], ['C', 'D', 'E']]%%
-On constate que chaque combinaison trouvée est unique.
-Par exemple %%['A', 'C', 'E']%% est le seul groupement de A, C et E de toute la liste.
-Mais pour les arrangements, à ce groupement correspondra toutes les permutations de A, C et E, c'est à dire: %%['C', 'A', 'E'], ['C', 'E', 'A'], ['E', 'C', 'A'], ['E', 'A', 'C'], ['A', 'E', 'C'], ['A', 'C', 'E']%%. Idem pour toutes les autres combinaisons trouvée.
-Voici le code correspondant. Il est directement issu de combinliste(), et donc... de partiesliste():
-<code python>
-def arrangliste(seq, k):
-    """Liste des arrangements des objets de la liste seq pris k à k"""
-    p = []
-    i, imax = 0, 2**len(seq)-1
-    while i<=imax:
-        s = []
-        j, jmax = 0, len(seq)-1
-        while j<=jmax:
-            if (i>>j)&1==1:
-                s.append(seq[j])
-            j += 1
-        if len(s)==k:
-            v = permutliste(s)
-            p.extend(v)
-        i += 1
-    return p
-</code>
-Exemple d'utilisation:
-<code python>
+===== Arrangements =====
-print arrangliste(['A','B','C'],2)  # affiche [['B', 'A'], ['A', 'B'], ['C', 'A'], ['A', 'C'], ['C', 'B'], ['B', 'C']]
-</code>
-==== Liste des arrangements d'une chaine de n caractères pris k à k ====
-C'est le même principe, à part que la donnée est une chaîne, et qu'on cherche tous les arrangements de k caractères de cette chaîne de longueur n.
-La solution la plus simple est d'utiliser la fonction précédente:
-<code python>
-def arrangchaine(ch,k):
-    return [''.join(X) for X in arrangliste(list(ch),k)]
-</code>
-Exemple d'utilisation:
-<code python>
-print arrangchaine('ABCD',3)  # affiche ['CAD', 'CDA', 'DCA', 'DAC', 'ADC', 'ACD', 'BAD', 'BDA', 'DBA', 'DAB', 'ADB', 'ABD', 'BAC', 'BCA', 'CBA', 'CAB', 'ACB', 'ABC', 'CBD', 'CDB', 'DCB', 'DBC', 'BDC', 'BCD']
-</code>
-\\
-Amusez-vous bien!
 <html>

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Différences

Outils de la page