Rang/Ordre d'une permutation

[invite29dc2068]

Bonjour,

Voila, je suis entrain de développer un programme informatique, mais ma requête ne nécessite aucune connaissance en programmation.

- J'ai quatre chiffres : 1,2,3 et 4
- En les combinant pour former des nombres à 4 chiffres (sans répetition d'un chiffre dans le meme nombre), j'obtiens 24 possibilités (4!=24).
- Ces nombres, je peux les classer par ordre croissant.
- Le plus petit : 1234 sera classé 1, le suivant, 1243=>2 , 1324=>3 jusqu'à 4321=>24
- Y'a t'il une formule qui me permet à partir de ABCD de retrouver son rang n ? Si oui, la réciproque est-elle possible ? pouvons nous generaliser ceci à des nombres à x chiffres ?

Remarque 1 : Mathematiquement parlant, il s'agit de determiner le rang/l'ordre d'un 4-tuplet issu de permutations de l'ensemble {1,2,3,4}.

Remarque 2 : Je suis persuadé que la solution existe puisque lorsque j'avais découvert le langage binaire, on m'a expliqué qu'on pouvait retrouver la valeur d'une séquence de 0 et de 1 grâce à la méthode des puissances de 2..Sauf que dans ce cas, les repetitions sont permises...

Remarque 3 : j'ai essayé une courbe de tendance sur Escel...C'est dire mon desespoir..

Remarque 4 : Une autre façon de voir les choses serait de poser la question de cette maniere : "g le nombre 3214, je veux connaitre son rang...Bon, le nombre commence par 3, donc son rang maximal serait 3!=18...Le 2eme chiffre commence par 2, donc...(???la suite???)

Merci les amis !
Merci de votre interet !
-----

[invite636fa06b]

Bonjour

Il n'existe pas de formule qui te permette de passer d'une permutation à une autre, il me semble avoir quelque chose dans "pour la sciences" il y a moins d'un an.
Je regarde...

[doryphore]

Le quatrième chiffre étant implicitement donné par la donnée des trois premiers, il n'intervient pas dans la formule, c'est déjà ça.

[danyvio]

Je regarde aussi. C'est un problème très intéressant. On doit pouvoir intrinsèquement calculer (sans comparer à la liste) le nombre de permutations qui amènent de 1234 à ABCD, sachant que de 1234 à 1234 il y 0 permutations , de 1234 à 1243 il y en a 1 etc. Mais cet etc est à formuler. A suivre ...

[A voir en vidéo sur Futura]

[doryphore]

Alors, j'ai 6(a-1)+...
Danyvio, tu parles des transpositions...

[doryphore]

Alors, j'ai 6(a-1)+2(b-1)+c où a est le premier chiffre de l'écriture de la permutation sous la forme (1243).
b est la position du 2ème chiffre dans l'ensemble ordonné {1,2,3,4} privé de a et c la position du troisième chiffre dans l'ensemble ordonné {1,2,3,4} privé du premier et du deuxième chiffre del'écriture de la permutation.

[invite636fa06b]

Oui, tu attribues bien un rang à chaque permutation, il ne te reste plus qu'à l'inverser : comment écrire la permutation qui porte le N° 13 ?
Je ne retrouve pas l'article que j'évoquai.
En fait, le plus simple pour engendrer la totalité des permutations est de programmer ce que l'on fait "à la main", c'est à dire faire la permutation qui donne l'accroissement mimimal

[doryphore]

La division euclidienne de 13 par 6(=3!) me donne (2,1) donc ça commence par 2+1=3. Je considère l'ensemble {1,2,4}. Je retranche 1 au reste. La division euclidienne de 0 par 2(=2!) me donne (0,0) le chiffre suivant est le 0+1 eme (i.e le 1). Je considère l'ensemble {2,4}. Le reste 0 de la précédente division m'indique que le troisième chiffre de la permutation est le 0+1 emme de l'ensemble considéré soit 2.
La permutation cherchée est (3,1,2,4)

[invite9f74ae56]

Et on peut generailser la formule de doryphore a l ensemble {1,2,...,n}, la formule devient:
(n-1)!(a1-1)+(n-2)!(a2-1)+... si on cherche l ordre dans le classement du nombre (a1,a2,...,an)

[invité576543]

Bonjour,

Sauf erreur, c'est une variante d'un problème qui a été posé il y a quelques mois, sur la numérotation des combinaisons du tirage du loto. Le cas du loto était les extraits de 6 nombres pris dans 49, ici il s'agit de 4 nombres pris parmi 4.

Je renvoie donc à cette discussion, http://forums.futura-sciences.com/thread101898.html

- Y'a t'il une formule qui me permet à partir de ABCD de retrouver son rang n ? Si oui, la réciproque est-elle possible ? pouvons nous generaliser ceci à des nombres à x chiffres ?

La réponse est donc oui, et elle est généralisable à toute liste des p nombres pris parmi n.

Cordialement,

[invite636fa06b]

Bonsoir,

Et oui, vous avez raison, j'ai retrouvé l'article en question : pour la science mars 2006 page 62 (le matelas et la théorie des groupes)
Il dit simplement que l'on ne peut pas trouver une transformation mécanique systématique qui permettrait de passer d'une permutation à l'autre...

[danyvio]

Ce problème m'intéressait, j'ai donc fait une petite étude personnelle. Le résultat (empirique à démontrer) est celui ci pour trouver le rang d'une combinaison.
1) Les combinaisons sont numérotées de 0 à 23
3) A chaque combinaison de 4 caractères j'associe trois chiffres déteminés ainsi :

Le premier est le nombre de caractères à droite du premier et qui lui sont inférieurs
Le deuxième est le nombre de caractères à droite du second et qui lui sont inférieurs
Le troisième est le nombre de caractères à droite du troisième et qui lui sont inférieurs.

Je multiplie le premier nombre par 3! soit 6
le deuxième par 2! soit 2
le troisième par 1! soit 1
en additionnant les résultats obtenus, et .... j'ai le rang !!

EX : ABCD -> 000 -> 000 ok
DCBA -> 321-> 3*6 + 2*2 + 1 = 23

BDAC -> 120 > 6+4 = 10

[invite29dc2068]

Wow, merci les amis, y'en a de la ressource !

Un Merci special à Danyvio : J'ai testé ta méthode sur Excel, c'est impeccable.
Le comptage d'elements inferieurs à droite d'un chiffre dans le nombre reste à être formalisé dans le programme, c'est lourd, mais fonctionnel..
Il reste cependant la méthode inverse : Un rang ---> Le nombre correspondant, et qu'en est-il pour un nombre à n chiffres, t'as testé ?

Blouseman et Doryphore : Je comprends pas, votre formule me donne 8 reponses correctes sur 24..L'avez vous testée ?

MMY : Effectivement, l'informaticien de la française des jeux ( ) a formulé un problème similaire au mien, j'arrive pas à en sortir la formule définitive !
http://forums.futura-sciences.com/thread101898.html

Vraiment merci les ami(e)s, pour l'instant Danyvio tient ze methode (mais à sens unique me parait-il).

Encore !!

[danyvio]

Vraiment merci les ami(e)s, pour l'instant Danyvio tient ze methode (mais à sens unique me parait-il).

Merci ! Ma modestie proverbiale en souffre Je vais réfléchir au problème inverse

[danyvio]

Le comptage d'elements inferieurs à droite d'un chiffre dans le nombre reste à être formalisé dans le programme, c'est lourd, mais fonctionnel..

N'oublions pas la merveilleuse instruction NB.SI qui permet par exemple de compter les cellules d'un champ dont la valeur est < à la valeur d'une cellule donnée.
Ci dessous extrait d'un fichier Excel :

=NB.SI(C3:$E$3;"<"&B3)

B3 contient le caractère de gauche, C3 D3 E3 les 3 suivants
La commande ci dessous compte les celleules de C3:E3 dont contenu < valeur de B3.

[invité576543]

MMY : Effectivement, l'informaticien de la française des jeux ( ) a formulé un problème similaire au mien, j'arrive pas à en sortir la formule définitive !
http://forums.futura-sciences.com/thread101898.html

Elle est au message #12, mais en relisant le problème posé, je me rend compte qu'il est un différent, même s'il est du même genre.

Je vais regarder plus en détail ce fil-ci, du coup ça semble complémentaire à l'autre!

Cordialement,

[danyvio]

Contre tout attente, aller du rang vers la combinaison semble moins simple. Une solution existe, qu'on pourrait appeler : "de l'art d'accomoder les restes" :

Soit le rang de 0 à 23. Au début du calcul, les quatre lettres ABCD sont « à placer ».

On divise le rang par 3! Le Quotient 0 à 3 donne l’indice de la lettre parmi ABCD (0-> A, 1-> B etc) Dans la suite, les indices vont toujours de 0 à ..

Le reste de la division par 6 est lui-même divisé par 2 !
Le quotient donne l’indice de la lettre parmi les trois lettres non attribuées.

Le reste est 0 ou 1, qui est l’indice de la lettre parmi les deux restantes.
Enfin il reste une lettre à attribuer.

Exemple Rang = 23
23 :6=3 reste 5
3-> D Il reste les lettres ABC
5 :2=2 reste 1

2-> C reste AB
1-> B reste A

Donc 23-> DCBA

Rang 15
15 :6=2 reste 3
2->C reste ABD
3 :2=1 reste 1

Le quotient 1-> B reste AD
Le reste 1-> D reste A
Combinaison : CBDA