NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 21/04/2017

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

RUBRIQUE   Nombres

 

Débutants

Général

Formes permutées

 

Glossaire

Général

 

INDEX

 

Permutations

 

Motifs

 

Général

Divisibilité

12345

Algorithme simples

Algorithmes rapides

 

Sommaire de cette page

>>> Logiciels mathématiques

>>> Méthode lexicographique

>>> Par insertion (Bottom-up)

>>> Par sous-permutations (Heap)

>>> Algorithme et programmation

>>> Steinhaus-Johnson-Trotter (SJT)

>>> STJ pour quatre éléments

>>> Une belle histoire de cloches

>>> Complexité et rapidité d'exécution

>>> Anglais

 

 

 

 

PERMUTATIONS

Algorithmes et leurs performances

 

Il existe plusieurs méthodes pour produire toutes les permutations d'un ensemble d'objets.

 

On rappelle qu'une liste de n éléments engendre n! (factorielle n) cas de permutations. Par exemple, 3 628 800 cas pour n = 10. Même avec les moyens actuels, il est impossible de dresser toutes les permutations au-delà de n = 15. Si le calcul pour n = 10 dure une seconde pour n = 15, il faudrait 100 heures soit un peu plus de 4 jours et, surtout, une grande quantité de pages pour les écrire.

 

Avec l'arrivée des ordinateurs, les mathématiciens et les informaticiens ont étudié les meilleurs algorithmes pour minimiser le temps d'exécution. Les plus rapides sont ceux qui occasionnent un seul mouvement de permutation par itération. C'est le cas pour l'algorithme de Heap et l'algorithme de Steinhaus-Jonhson-Trotter. Le premier (Heap) est sans doute plus simple à implémenter.

Compte tenu de l'usage des permutations, la vitesse de calcul n'est pas d'une grande importance. La recherche d'améliorations est cependant un excellent moyen de faire progresser la science de l'algorithmique.  

 

 

Logiciels mathématiques

La majorité des logiciels mathématiques incorpore la fonction permutation. Exemple avec Maple:

 

 

Méthode lexicographique

Les algorithmes les plus simples produisent les permutations classiques par ordre lexicographique (alphabétique et nombres croissants). Le logiciel de permutation Maple utilise ce procédé.

 

Exemple: n = 4 avec chiffres

[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]

Exemple: n = 3 avec mots

[Riri, Fifi, Loulou], [Riri, Loulou, Fifi], [Fifi, Riri, Loulou], [Fifi, Loulou, Riri], [Loulou, Riri, Fifi], [Loulou, Fifi, Riri]

 

Suite et programmation expliquée en détail en Récursivité

 

Voir Permutations des lettres dans un mot (calcul des permutations et arrangements)

 

 Méthodes plus sophistiquées et plus rapides

 

Algorithme par insertion  (Bottom-up)

 

Une première idée de production des permutations

Les deux premiers éléments (noirs) sont permutés.

L'élément suivant (bleu puis rouge) est inséré entre chaque espace entre les éléments déjà placés.

 

Définition récursive:

1) trouvez toutes des permutations avec n – 1 éléments; et

2) insérez les éléments restants dans tous les espaces possibles des éléments de la permutation n – 1.

 

 

 

 

 

 

Algorithme par sous-permutations (Heap)

Principe de l'algorithme de Heap

 

On fixe le premier élément A et on permute le reste  (BCD).

Pour permuter le reste, on fixe le premier élément (B) et on permute le reste (CD).

Etc.

 

Méthode, comme on le voit récursive (méthode qui fait appel à elle-même)

 

Méthode à modification minimale, puisque chaque permutation est obtenu à partir de la précédente avec une simple permutation de deux éléments.

En pratique

L'algorithme de Heap est souvent présenté dans l'autre sens (plus pratique pour sa programmation).

Les éléments fixes sont à droite et on permute ce qui reste à gauche.

 

123

213

 

312

132

 

231

321

 

Départ.

Le 3 est fixe, permutation des deux premiers.

Permutation des deux extrémités.

Le 2 est fixe, permutation des deux premiers.

Permutation des deux extrémités.

Le 1 est fixee, permutation des deux premiers.

 

 

 

Algorithme de Heap – Principe

 

Permutation d'une chaîne comptant n éléments

 

L'algorithme (procédure) engendre les (n – 1)! permutations des n – 1 premiers éléments. Le dernier élément étant fixé.

La procédure fait appel à elle-même, en cascade pour n de plus en plus petit (procédure récursive).

 

Si n  = 1, la récursivité de ce niveau est atteinte et le programme délivre une des permutations.

Sinon, la procédure s'appelle elle-même pour le n immédiatement inférieur (n – 1).

 

Après travail aux niveaux inférieurs, le programme est de retour à ce niveau de récursivité, le programme opère la permutation magique de Heap

*       si n est pair, on permute l'élément i avec le dernier (n);

*       si n est impair, on permute les éléments extrêmes (1 et n).

 

Programmation de l'algorithme de Heap

Méthode récursive

 

 

 

Vous reconnaissez exactement l'algorithme indiqué. Son implémentation sous Maple est assez simple; de même que sous bien d'autres logiciels.

 

Le secret du fonctionnement tient dans la distinction en local et global. Faute de le faire, vous allez vous arracher les cheveux à la mise au point!

 

La chaine à permuter (ici AA) doit être déclarée en GLOBAL (et non en local). Sinon Le programme en remontant une étape de récursion, oublie la permutation qu'il a effectuée. Il reprend la permutation qu'il a mémorisée en local, c'est-à dire au niveau k de la récursivité et non aux niveaux plus profonds où il a travaillé.

 

 

Note: ce programme retourne la liste des permutations avec lprint en 5e ligne. Je n'ai pas trouvé l'astuce qui permettrait de retourner une liste avec return.

Si quelqu'un sait je suis preneur!

 

En rouge, programme demandant la permutation de 5 éléments.

 

N est la quantité d'éléments obtenue par nops(A). On aurait tout aussi bien pu l'écrire directement.

 

En bleu, le début de la liste des 120 permutations.

 

 

 

 

 

 

 

Note aux programmeurs: vous trouverez ce même code sur divers sites Internet. Aucun ne marche correctement sans adaptation au langage utilisé.

Pour une raison qui m'est inconnue, Wikipedia (anglais) ajoute un extra appel à la procédure.

Voir ProgrammationIndex

 

 

 

 

Algorithme de Steinhaus-Johnson-Trotter

Algorithme classique de permutations

Algorithme SJT de permutations

Les algorithmes classiques délivrent les permutations à partir d'un ordre lexicographique (alphabétique ou croissants pour les nombres).

Ces algorithmes fonctionnent par propagation.

Cet algorithme  (comme Heap) délivre une permutation à chaque opération et dans un ordre particulier.

Cet algorithme fonctionne par cheminement direct parmi toutes les permutations.

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

1 2 3

1 3 2

3 1 2

3 2 1

2 3 1

2 1 3

Découvert indépendamment par Johnson et Trotter vers 1960 et même avant sous une certaine forme par Steinhaus. >>>

 

 

Principe de l'algorithme SJT

 

Le graphe de toutes les permutations forme un polyèdre. L'astuce consiste à parcourir un chemin hamiltonien entre les sommets (chemin qui passe une fois et une seule par tous les sommets).

Cela rappelle le code binaire Gray qui change un seul bit pour passer d'un nombre binaire à un autre.

On commence par écrire tous les éléments dans l'ordre croissants

1 2 3 (exemple)

On donne une direction identique à chaque élément au départ

Un nombre est mobile si le nombre pointé est plus petit.

Les nombres aux extrémités et pointant vers l'extérieur ne sont pas mobiles.

Ci-dessus les nombres 2 et 3  sont mobiles

1) Prendre l'élément mobile le plus grand et permuter avec le voisin pointé.

2) Vérifier s'il existe des plus grands mobiles. Si oui, changer leur direction

ici, non

3) Sinon, poursuivre avec le plus grand en cours de traitement (3).

Cet élément est en bout de course, alors, reprendre l'étape 1.

Y'a-t-il un plus grand que le 2, oui le 3, alors on inverse le sens.

Ce nombre 3 redevient le plus grand mobile.

Nouvelle possibilité de permutation.

Aucun n'est mobile.

Fin

 

Algorithme STJ générique

Mettre les éléments dans l'ordre croissant.

Tant qu'il existe un élément mobile:

*       Trouver l'élément mobile M le plus grand;

*       Permuter ce nombre M et son voisin pointé; et

*       Changer la direction de tous les nombres plus grands que M. 

 

 

 

 

STJ avec quatre nombres

 

Les 24 étapes de permutation avec configuration et explications.

 

Le sens associé à chaque nombre est symbolisé par un point.

 

 

 

 

1

.1

.2

.3

.4

Configuration initiale

2

.1

.2

.4

.3

4 est le plus grand

Inversion 3 et 4 (jaune)

3

.1

.4

.2

.3

id.

4

.4

.1

.2

.3

id.

5

4.

.1

.3

.2

4 est immobilisé

3 devient le plus grand

4 > 3 est inversé (bleu)

6

.1

4.

.3

.2

4 est le plus grand mobile

7

.1

.3

4.

.2

id.

8

.1

.3

.2

4.

id.

9

.3

.1

.2

.4

4 est immobilisé

3 devient le plus grand

4 > 3 est inversé

10

.3

.1

.4

.2

4 est le plus grand mobile

11

.3

.4

.1

.2

id.

12

.4

.3

.1

.2

id.

13

4.

3.

.2

.1

4 et 3 sont immobilisés

2 devient le plus grand

Inversion de 4 et 3, car > 2

14

3.

4.

.2

.1

4 est le plus grand mobile

15

3.

.2

4.

.1

id.

16

3.

.2

.1

4.

id.

17

.2

3.

.1

.4

4 est immobilisé

3 devient le plus grand

4 > 3 est inversé

18

.2

3.

.4

.1

4 est le plus grand mobile

19

.2

.4

3.

.1

id.

20

.4

.2

3.

.1

id.

21

4.

.2

.1

3.

4 est immobilisé

3 devient le plus grand

4 > 3 est inversé

22

.2

4.

.1

3.

4 est le plus grand mobile

23

.2

.1

4.

3.

id.

24

.2

.1

3.

4.

Aucune mobilité, car chacun regarde vers plus grand ou le vide.

 

Permutoèdre

Permutohedron

 

Nom donné par Guilbaud & Rosenstiehl  en 1963.

Schoute fut le premier à étudier ces polyèdres en 1911.

 

Source image: Wikipédia

 

Cheminement à travers le graphe des permutations classiques (simple exercice)

 

 

Une belle histoire du XVIIe siècle en Angleterre

Un groupe de personnes forme un cercle. Chacun doit faire sonner une grosse cloche à l'aide d'une corde. Pour éviter la monotonie de la mélodie, la séquence doit être régulièrement changée. Or, chaque cloche tinte durant un bon moment et ne peut pas être relancée trop rapidement. Par exemple, la cloche actuellement en 3e position ne pourra jouer qu'en 2e ou en 4e.  Le passage d'une permutation à la suivante avec une seule permutation était donc déjà connue à cette époque.

 

 

 

Complexité et rapidité

Définitions

Complexité en O (n! . n).

Si une opération dure t secondes, il faudra faire n! manipulations pour le n! permutations fois n manipulations pour les n éléments de la chaine à permuter.

La durée d'exécution sera : n! . n . t secondes.

C'est celle valeur qui est souvent donnée pour l'exécution des algorithmes classiques

Complexité en O (n!).

Impossible de réduire la quantité d'opération à moins que la quantité de permutations (n!).

C'est cette valeur qui est donné pour l'exécution de l'algorithme SJT.

Étude de Youssef Bassil (2012)

 

Alors que les algorithmes se valent jusqu'à une longueur de n =6 éléments à permuter, l'algorithme SJT supplante nettement les valeurs de n supérieures. C'est le cas également avec l'algorithme de Heap

 

L'auteur donne pour une longueur 10:

*       Algorithme par insertion: 15 à 17 secondes

*       Algorithme SJT: 3,2 à 3, 5 secondes

Un rapport égal à 5 qui croit encore avec la longueur à permuter.

Voir Référence

Nouveautés

Ces algorithmes sont régulièrement améliorés et d'autres voient le jour comme:

*       Fike en 1975, et

*       Ives en 1976

 

Malgré une certaine complexité du codage, il est vrai que l'algorithme SJT et l'algorithme de Heap sont les seuls à produire une configuration à partir de la précédente avec une seule permutation de deux éléments adjacents.

 

Les permutations obtenues sont également sans symétrie: une moitié ne contient aucune réflexion d'une configuration appartenant à l'autre moitié.

 

 

English corner

 

Keywords: Permutation, algorithms, brute force, divide and conquer.

 

Permutation is the different arrangements that can be made with a given number of things taking some or all of them at a time. The notation P(n,r) is used to denote the number of permutations of n things taken r at a time. Permutation is used in various fields such as mathematics, group theory, statistics, and computing, to solve several combinatorial problems such as the job assignment problem and the traveling salesman  problem. 

 

Bottom-Up, Lexicography, and Johnson-Trotter are three of the most popular permutation algorithms that emerged during the past decades.

 

Generally speaking, the Johnson-Trotter algorithm checks to see whether a mobile number exists or not, if yes the algorithm performs the following:

*       find the largest mobile element k,

*       swap k and the adjacent element it is facing,

*       reverse the direction of all elements larger than k, and

*       as long as there exists a mobile repeat all the above.

 

 

 

 

 

Suite

*     Comment programmer les permutations

*       PermutationsIndex

Voir

*     Divisibilité des nombres permutés

*       Formes permutées

*       Récursivité et sa programmation

Sites

*        Steinhaus–Johnson–Trotter algorithm - Wikipedia

*        Steinhaus Johnson Trotter permutation algorithm explained and implemented in Java – Tropenhize -  Source d'inspiration pour cette page.

*        Counting and listing all permutations -  Cut The Knot

*        Johnson-Trotter Algorithm, Listing All Permutations – Cut The Knot

*        A Comparative Study on the Performance of Permutation Algorithms – Youssef Bassil (2012) – Description des méthodes, du code à produire et des performances de chaque algorithme.

*        Evaluation of permutation algorithms – M.K. Roy (1976) – Ce papier évalue les performances des sis meilleurs algorithmes de permutations. Très technique et conclusions pas faciles à discerner!

*        Permutation Generation Methods – Robert Sedewick (1977) – Revue des méthodes de permutations

*       PermutationsRosettacode – Programmes de permutations décrit pour plus de 80 langages.

Cette page

http://villemin.gerard.free.fr/aNombre/MOTIF/PermutAl.htm