Répondre à la discussion
Affichage des résultats 1 à 17 sur 17

Rang/Ordre d'une permutation



  1. #1
    djwaas

    Rang/Ordre d'une permutation


    ------

    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 !

    -----

  2. Publicité
  3. #2
    zinia

    Re : Rang/Ordre d'une permutation

    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...

  4. #3
    doryphore

    Re : Rang/Ordre d'une permutation

    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.
    "Plus les choses changent et plus elles restent les mêmes..." Snake Plisskein

  5. #4
    danyvio

    Re : Rang/Ordre d'une permutation

    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 ...
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  6. A voir en vidéo sur Futura
  7. #5
    doryphore

    Re : Rang/Ordre d'une permutation

    Alors, j'ai 6(a-1)+...
    Danyvio, tu parles des transpositions...
    Dernière modification par doryphore ; 25/11/2006 à 14h24. Motif: croisement
    "Plus les choses changent et plus elles restent les mêmes..." Snake Plisskein

  8. #6
    doryphore

    Re : Rang/Ordre d'une permutation

    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.
    "Plus les choses changent et plus elles restent les mêmes..." Snake Plisskein

  9. Publicité
  10. #7
    zinia

    Re : Rang/Ordre d'une permutation

    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

  11. #8
    doryphore

    Re : Rang/Ordre d'une permutation

    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)
    "Plus les choses changent et plus elles restent les mêmes..." Snake Plisskein

  12. #9
    blouseman

    Re : Rang/Ordre d'une permutation

    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)

  13. #10
    invité576543
    Invité

    Re : Rang/Ordre d'une permutation

    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,

  14. #11
    zinia

    Re : Rang/Ordre d'une permutation

    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...

  15. #12
    danyvio

    Re : Rang/Ordre d'une permutation

    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
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  16. Publicité
  17. #13
    djwaas

    Re : Rang/Ordre d'une permutation

    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 !!

  18. #14
    danyvio

    Re : Rang/Ordre d'une permutation

    Citation Envoyé par djwaas Voir le message
    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
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  19. #15
    danyvio

    Re : Rang/Ordre d'une permutation

    Citation Envoyé par djwaas Voir le message
    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.
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  20. #16
    invité576543
    Invité

    Re : Rang/Ordre d'une permutation

    Citation Envoyé par djwaas Voir le message
    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,

  21. #17
    danyvio

    Re : Rang/Ordre d'une permutation

    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
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

Discussions similaires

  1. Rang d'une matrice !!
    Par chentouf dans le forum Mathématiques du supérieur
    Réponses: 9
    Dernier message: 11/09/2007, 22h24
  2. Rang d'une matrice
    Par Bleyblue dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 09/04/2007, 16h48
  3. Le rang d'une matrice
    Par nams2590 dans le forum Mathématiques du supérieur
    Réponses: 15
    Dernier message: 20/03/2007, 09h20
  4. Ordre d'un groupe de permutation
    Par Bleyblue dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 02/01/2007, 19h14
  5. Rang d'une matrice.
    Par lolouki dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 17/09/2006, 11h20