|
Édition du: 19/11/2023 |
|
INDEX |
PERMUTATIONS |
||
Faites un double-clic pour un retour en haut de page
|
PERMUTATIONS Page
introductive sur les permutations. Exemples et définition. Présentation de
divers types de permutations. |
||
|
|
Sommaire de cette page >>> Permutations linéaires >>> Permutations figurées >>> Permutations circulaires >>> Permutations sous-contrainte >>> Permutations singulières >>> Programmation |
Débutants Glossaire |
Permuter, permutation –
Linguistique
|
|
|
Permutations (sans répétition) Toutes les manières de positionner n objets les
uns à côté des autres sur une ligne. Quantité de permutations Ayant choisi le premier objets, il en reste n – 1
; ayant choisi le suivant il en reste n – 2; etc. Soit un total: P(n) = n (n – 1) (n – 2) … 3
· 2 · 1 = n! |
Les six possibilités de disposer
les nombres: 1, 2 et 3 123, 132, 213, 231, 312, 321 |
|
|
Permutations avec répétition Les objets considérés peuvent être ne double,
triple … Les objets répétés sont identiques et donc non
identifiables.
|
Permutation avec 1, 2, 2, 3 Quantité: 4! / 2! = 24 / 2 = 12 1223, 1232, 1322, 2123, 2132, 2213, 2231, 2312, 2321, 3122, 3212, 3221 |
|
|
Représentation en grille:
permutations de Lucas ou permutations
figurées Elles ont été introduites en 1883 par le
mathématicien Édouard
Lucas. Avec trois objets, on peut adopter cette
représentation sur une grille 3 x 3 d'une permutation linéaire de trois
éléments:
On liste les objets par colonne croissante en
indiquant la ligne sur laquelle il se trouve. Ce principe de représentation des permutations
linéaires impose qu'il n'existe qu'un seul objet par ligne et par colonne.
Et, bien sûr, cette construction conduit à énoncer tous les cas possibles. Avec quatre objets: 4! = 24
possibilités
Carré latin Cette représentation est utilisée pour former les
carrés
latins: ce sont des sortes de carrés magiques simplifiés pour lesquels,
sur une grille n x n, on dispose n fois n objets à raison d'un objet unique
par ligne et par colonne. Exemple de
carré latin 3x3
Avec les nombres de 1 à n dans le carré latin, la
somme sur les lignes et sur les colonnes est constante et vaut la somme des nombres
de 1 à n soit n (n + 1) / 2. |
|
Voir Brève
47-938
|
Applications
des permutations en grille |
||
|
La représentation figurée
en grille des permutations linéaires est implicitement utilisée dans de
nombreuses applications utilisant des grilles |
Permutations figurées
Par extension
|
|
|
Permutation circulaire simple Les éléments d'une liste sont tous décalés d'un cran
et le premier repasse en dernier ou
inversement selon le sens du décalage. |
A, B, C, D, E B, C, D, E, A |
|
|
Transposition Permutation simple qui correspond à une simple
inversion de deux éléments. |
A, B, C, D, E A, B, D, C, E |
|
Voir Nombres
permutations
|
Permutations sous-contraintes Permutations linéaires soumise à des conditions
souvent sur les nombres qui la composent. |
1234 est croissante 3421 est décroissante |
|
|
Permutations d'Euler Permutations portant sur des nombres. On ne
retient que celles pour lesquelles les nombres vont en croissant (ou en
décroissant). Voire même sur une quantité définie de ces
croissances. Voir SUITE |
1 3 2 4 Cette suite présente deux croissances (1, 3) et
(2, 4). |
|
|
Permutations ondulantes d'Euler Permutations dont les nombres croissent puis
décroissent. Voir SUITE |
1 3 2 4 est de ce type avec les croissances (1, 3) et (2, 4)
et la décroissance (3, 2). |
|
|
Permutations symétriques Permutations de nombres tels que la somme des nombres
à égale distance des extrêmes est la même. Les permutations figurées correspondantes sont
alors symétriques par rapport au centre de la grille. |
1 3 2 4 répond à cette exigence: 1 + 4 = 3 + 2 |
|
Les huit permutations symétriques
sur grille 4x4
|
Permutations spirales ou sextines Permutation où les objets situés dans la seconde
moitié s'intercalent entre ceux de la première moitié en ordre décroissant. Voir SUITE |
123456 devient 61
52 43 |
|
|
Instruction existante
|
Commentaires Le logiciel mathématique Maple, et la majorité de ces
logiciels, disposent d'une instruction particulière accédant directement aux
permutations. En bas, appel direct avec le logiciel combinat et
exemple d'une liste explicite. |
||
|
Principe de programmation par récursion
(backtracking)
Voir Algorithmes
de recherche des permutations |
|||
|
Programme
Python
Source Rosetta
code – Autres langages disponibles |
Commentaires On définit une fonction permutation. L'instruction list(range(3))
retourne la liste [0, 1, 2], par exemple. Dans le reste du programme, l'instruction la plus
importante et la plus déroutante est yield
(produire). En gros, elle permet de retenir le résultat du dernier calcul qui
reste disponible pour la prochaine itération (le prochain " tour de
piste"). Elle évite de conserver tous les résultats antérieurs qui
encombreraient la mémoire inutilement. |
||
Voir Programmation – Index / Suites sur
programmation des permutations avec récursivité
Haut de page (ou
double-clic)
|
Retour |
|
|
Suite |
|
|
Voir |
|
|
Livre |
|
|
Sites |
|
|
Cette page |