Discussion :

[pseudocode]

Merci d'utiliser les balises [code] pour afficher des sources sur le forum.

[JeitEmgie]

Je veux dire une transposition équivalente à deux transpositions

? c'est possible çà ?
quand on n'a aucun élément déjà en place et qu'on commence par les permutations qui mettent 2 éléments à leur place ?


pour le code :

on doit toujours exécuter les 2 boucles mais on peut quitter la deuxième boucle et recommencer à la première s'il y a une permutation dans cette deuxième…
on quitte le tout quand il n'y a plus eu de permutation dans aucune des deux…

[pseudocode]

? c'est possible çà ?

Normalement non. Le nombre de transpositions doit avoir la meme parité. On peut chercher à remplacer 4 transpositions par 2 transpositions, ou 3 par 1... mais pas 2 par 1.

[JeitEmgie]

Normalement non. Le nombre de transpositions doit avoir la meme parité. On peut chercher à remplacer 4 transpositions par 2 transpositions, ou 3 par 1... mais pas 2 par 1.

chuuut : la question c'était pour faire réfléchir Onimaru…

[pseudocode]

chuuut : la question c'était pour faire réfléchir Onimaru…

Ah, mince. j'aurais du mettre des balises spoiler

[Onimaru]

Salut les pros ,
Vous me prenez pour qui ?
Ce que vous dites sera vrai si on parle de la même permutation (vous parlez de la signature : je peux ajouter deux transpositions identiques et le résultat reste le même), mais dans notre problème il faut trouver la plus petite permutation.
Comme d'après vous il n y a pas une méthode claire pour faire ça j'ai le droit de penser à autre chose comme trouver une permutation et essayer de la réduire : c'est une autre permutation qui a une autre signature.
pour faire cette réduction (au niveau des transpositions) il ne faut pas se baser seulement sur les indices mais aussi sur la valeur correspondante à cet indice.

Exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
 T := A; 
 for I := 1 to N do
  if B[I] <> T[I] then // pour laisser les points fixes.
   for J := I + 1 to N do // on cherche la première position qui satisfait la 
                                // condition.
     if B[I] = T[J] then // on cherche la transposition.
      begin
       AddTransposition(AsTransposition(I, J)); // ajouter cette transposition à 
                                                              // la permutation.
       Swap(T, AsTransposition(I, J)); // Modifier le vecteur temporaire.
       Break // pour ne pas ajouter une autre transposition pour le même 
               // élément.
      end;

Après l'exécution de cet algorithme j'ai fait une boucle pour réduire certaines transpositions avec cette "loi" :
(a, b) , (b, c) deux transpositions.
(b), (c) les valeurs correspondantes aux indices b et c.

(a,b) , (b,c) et (b) = (c) ----> (a, c)

J'ai essayé ça marche mais elle ne donne pas le résultat demandé si on la compare par exemple au premier algorithme avec une boucle pour inversée.


[citation]
? c'est possible çà ?
quand on n'a aucun élément déjà en place et qu'on commence par les permutations qui mettent 2 éléments à leur place ?


pour le code :

on doit toujours exécuter les 2 boucles mais on peut quitter la deuxième boucle et recommencer à la première s'il y a une permutation dans cette deuxième…
on quitte le tout quand il n'y a plus eu de permutation dans aucune des deux…
[/citation]

pouvez vous écrire cet algorithme ?

Merci.

[Onimaru]

Désolé pour la balise qui n'existe pas : [citation].

[Invité]

Bonjour,
Je suis ce sujet depuis le début, et je pense que vous devriez aller voir du côté du tri à bulle.
Le critère ne serait pas une relation d'ordre, mais une relation d'identité entre A et B.

[Onimaru]

Bonjour,
Je suis ce sujet depuis le début, et je pense que vous devriez aller voir du côté du tri à bulle.
Le critère ne serait pas une relation d'ordre, mais une relation d'identité entre A et B.

Pouvez vous m'éclaire plus sur ce sujet ?

Merci.

[Invité]

Cela ne date pas d'hier.
Le principe est de parcourir une liste dans un sens.
Si on trouve 2 valeurs qui ne sont pas dans le bon ordre, on les échange, et on continue à parcourir la liste, mais dans l'autre sens, jusqu'à trouver sa place.
Comme on s'est souvenu de l'endroit où on est retourné en arrière, on repart de là et on continue.
J'ai vu qu'il y avait un article dans Wikipédia.
malheureusement je crois que c'est une invention française, mais les américains ont bien dû trouver une traduction.

[Onimaru]

Pouvez vous me dire où se trouve cet article pour le lire?

[Invité]

Une petite recherche dans Wikipedia, via Google, m'a permis de trouver cela assez vite.
http://fr.wikipedia.org/wiki/Tri_%C3%A0_bulles
Par ailleurs, je suppose que vos capacités de recherche et votre curiosité vous auraient permis de le trouver très vite aussi.

[Onimaru]

Salut Pierre Dolez,
Oui cet article je l'ai lu bien avant plusieurs fois mais je ne saisis pas comme il pourra m'aider dans mon problème, veuillez nous éclairer dans ce sujet.

[Nemerle]

1. L'algo cherche le premier element de A (de gauche a droite) qui n'est pas identique a celui de B, puis cherche dans les elements restant celui qu'il faudrait mettre.
2. L'algo effectue la permutation (et la note en mémoire).
3. retour à l'étape 1, tant que A est différent de B

Cet algo est correct dans le monde des permutations. Les gars, utilisons le langage standard:

- une permutation est une bijection de (1...n) vers (1...n)
- une transposition t(i,j) est la bijection switchant i et j et fixant le reste.

L'algo décrit par Pseudocode fournit une décomposition minimale d'une permutation en composition de transpositions. C'est minimal, au sens où c'est le job "minimum", comme on le voit avec la représentation en tresse des permutations ci-dessous (désolé, je dessine mal).




Donc ton exemple tu recherches une décomposition en transpositions te permettant de passant de ton vecteur A à B. Ok, c'est pas le monde des permutations, car des composantes de A et/ou B sont égales, mais Pseudo a adapté l'algo.Je pense qu'une précision s'impose dans son point 1:

1. L'algo cherche le premier element de A (de gauche a droite) qui n'est pas identique a celui de B, soit Ai<>Bi, puis cherche dans les elements Aj ou j>i le premier élément vérifiant Aj=Bi et Bj<>Aj. On applique alors la transposition T(i,j), et comme dans le dessin ci-dessus on arrive à une décomposition "minimale".

[Onimaru]

Ton idée parait intéressante et je crois c'est que je cherche pouvez vous l'écrire sous forme d'algorithme ? et moi de ma part je vais essayer.

[Onimaru]

(3,0,4,2,3,1,4,2,1)
(0,1,1,2,2,3,3,4,4)

0) From : 0 ,To : 1
1) From : 1 ,To : 8
2) From : 2 ,To : 5
3) From : 4 ,To : 7
4) From : 5 ,To : 8
5) From : 6 ,To : 7
------------------------------------

0) From : 8 ,To : 2
1) From : 1 ,To : 5
2) From : 5 ,To : 0
3) From : 7 ,To : 6
4) From : 6 ,To : 4

//////////////////////////////////////

(4,3,0,4,3,1,1,1,2,4,3,3,2,3,4,4,1,1,3,4,2)
(0,1,1,1,1,1,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4)

0) From : 0 ,To : 2
1) From : 1 ,To : 17
2) From : 2 ,To : 16
3) From : 3 ,To : 7
4) From : 4 ,To : 6
5) From : 6 ,To : 20
6) From : 7 ,To : 12
7) From : 9 ,To : 20
8) From : 12 ,To : 18
9) From : 14 ,To : 17
------------------------------------

0) From : 16 ,To : 3
1) From : 18 ,To : 9
2) From : 2 ,To : 7
3) From : 7 ,To : 20
4) From : 20 ,To : 14
5) From : 14 ,To : 4
6) From : 4 ,To : 17
7) From : 17 ,To : 0
8) From : 1 ,To : 6
9) From : 6 ,To : 12

//////////////////////////////////////

(1,1,1,3,0,4,1,2,2,2)
(0,1,1,1,1,2,2,2,3,4)

0) From : 0 ,To : 4
1) From : 3 ,To : 6
2) From : 5 ,To : 9
3) From : 6 ,To : 8
------------------------------------

0) From : 4 ,To : 0
1) From : 9 ,To : 5
2) From : 6 ,To : 8
3) From : 8 ,To : 3

J'ai essayé deux algorithmes sur trois paires de tableaux (A et B, B = A trié)
Les première partie : le premier algorithme avec la boucle pour descendante.
la deuxième partie : avec les orbites en prenant en considération au premier lieu les transpositions parfaites.

Je vais comparer ces résultats avec le futur algorithme de Nemerle et on va voir.

[pseudocode]

mais Pseudo a adapté l'algo.Je pense qu'une précision s'impose dans son point 1:

1. L'algo cherche le premier element de A (de gauche a droite) qui n'est pas identique a celui de B, soit Ai<>Bi, puis cherche dans les elements Aj ou j>i le premier élément vérifiant Aj=Bi et Bj<>Aj. On applique alors la transposition T(i,j), et comme dans le dessin ci-dessus on arrive à une décomposition "minimale".

Oui, mon explication n'était pas très rigoureuse mathématiquement parlant. J'essayais juste de résumer le principe de l'algo de Wikipedia en 3 phrases.

Ca m'apprendra.

[Onimaru]

Veuillez écrire cet algorithme pour moi et on discuteras bien, moi entre temps je vais le faire.

[Nemerle]

on stocke les transpositions (i,j) dans un vecteur T

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
i=1
tant que i<>n
    si a(i)<>b(i) alors
        j=i+1
        tant que (a(j)<>b(i) ou a(j)=b(j))
            j=j+1
        fin tant que
        T.ajouter(i,j)
        switch=a(j)   
        a(j)=a(i)
        a(i)=switch
    fin si
    i=i+1
fin tant que

[Onimaru]

on stocke les transpositions (i,j) dans un vecteur T

Merci Nemerle, je vais l'essayer