Discussion :

[Onimaru]

Salut à tous,
Voici le problème :
Soit L une liste de n éléments.
Soit L' une liste de n éléments obtenue à partir de L avec une permutation S qui est l'une des plus courtes (qui contiennent le plus petit nombre possible de transpositions).

Est ce qu'on peut trouver toutes les permutations courtes restantes à partir de S???

Merci.

[Aleph69]

Bonjour,

je ne comprend pas la question. Si S contient le plus petit nombre de transpositions, alors elle est unique et c'est celle qui n'en contient aucune.

[Onimaru]

Bonjour,

je ne comprend pas la question. Si S contient le plus petit nombre de transpositions, alors elle est unique et c'est celle qui n'en contient aucune.

Salut, le problème c'est quelle n'est pas unique.
Un exemple :
L = (2,2,3,3,2,4,0,0,4,2)
L' = (0,0,2,2,2,2,3,3,4,4)

Voici une permutation qui transforme L en L' :
(0,7)
(1,6)
(2,7)
(3,9)
(5,6)
(6,9)

Y a t il une permutation plus courte ?
Cette permutation est obtenue avec l'algorithme décrit à la fin de cette discution :
http://www.developpez.net/forums/d96...e-permutation/
D'après son auteur "Nemerle" c'est une permutation minimale.

Y a t il un théorème qui dit que cette permutation est unique?

On ce qui me concerne j'ai pu trouver une autre permutation avec la même longueur qui fait le même travail :
(0,6)
(1,7)
(2,4)
(3,6)
(4,7)
(5,9)

Si ce que tu dit est vrai alors l'algorithme en question ne donne pas la permutation la plus minimale.

[Aleph69]

Bonjour,

je n'avais pas compris la question. Pour les permutations minimales, je pense qu'il faut faire un peu de théorie des groupes pour comprendre comment les caractériser. Je suis étonné que tu n'ais pas trouvé de documentation sur le net.

[Onimaru]

Bonjour,

je n'avais pas compris la question. Pour les permutations minimales, je pense qu'il faut faire un peu de théorie des groupes pour comprendre comment les caractériser. Je suis étonné que tu n'ais pas trouvé de documentation sur le net.

Merci, je suis étonné comme toi
D'après ce que j'ai lu il faut peut être utiliser les cycles ou quelque chose de ce genre pour trouver les autres permutations mais je ne sais comment.

[Aleph69]

Il semblerait que l'algorithme donné dans Wilkipedia réponde à ton problème :
http://fr.wikipedia.org/wiki/Permuta....A9composition