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

[Onimaru]

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

Salut,
J'ai vu cet algorithme avant, mais je ne sais pas comment l'utiliser pour trouver les permutations équivalentes d'une autre permutation minimale.

[Aleph69]

Essaye peut-être de voir ce qui est fait là-dedans :
http://arxiv.org/PS_cache/arxiv/pdf/...010.5963v1.pdf

Sinon, tente de contacter Nermerle ou pose ta question sur des forums purement mathématiques (mathematex, les mathematiques.net).

Je ne connais pas assez le domaine pour pouvoir t'aider davantage.

[Onimaru]

Essaye peut-être de voir ce qui est fait là-dedans :
http://arxiv.org/PS_cache/arxiv/pdf/...010.5963v1.pdf

Sinon, tente de contacter Nermerle ou pose ta question sur des forums purement mathématiques (mathematex, les mathematiques.net).

Je ne connais pas assez le domaine pour pouvoir t'aider davantage.

Merci, pour le lien je crois qu'il fait l'affaire, il faut juste qu'on me l'explique un peu.

[Alp]

Le problème c'est qu'une décomposition de permutation en composée de transpositions n'est pas unique. Ce qui est unique, c'est la parité du nombre de transpositions utilisées.

Par contre, la décomposition d'une permutation quelconque en produit de cycles à supports disjoints est unique. Donc si tu veux une preuve/garantie d'unicité pour quelque chose, faut regarder la décomposition en produit de cycles à mon avis.

[Onimaru]

Le problème c'est qu'une décomposition de permutation en composée de transpositions n'est pas unique. Ce qui est unique, c'est la parité du nombre de transpositions utilisées.

Par contre, la décomposition d'une permutation quelconque en produit de cycles à supports disjoints est unique. Donc si tu veux une preuve/garantie d'unicité pour quelque chose, faut regarder la décomposition en produit de cycles à mon avis.

Merci.
Mais pour préciser : je veux dire des décompositions qui diffèrent d'une ou plusieurs transpositions et non des réarrangements des mêmes transpositions.
C'est de cette unicité que je parle.
Autrement dit : si on a une décomposition qui contient un minimum de transpositions, existera t ils d'autres décompositions qui diffèrent de la première en une ou plusieurs transpositions?

[Alp]

Si tu sais que c'est la (une, en fait) décomposition qui contient le moins de transpositions possible, alors tu peux être sur qu'une autre décomposition aura soit le même nombre n de transposition (c'est peut-être minimal mais ça ne veut pas dire que c'est la seule possibilité), soit n+2, soit n+4, etc.

[Onimaru]

Si tu sais que c'est la (une, en fait) décomposition qui contient le moins de transpositions possible, alors tu peux être sur qu'une autre décomposition aura soit le même nombre n de transposition (c'est peut-être minimal mais ça ne veut pas dire que c'est la seule possibilité), soit n+2, soit n+4, etc.

Je vois clair maintenant.

[Onimaru]

Salut
Une autre question si on a une décomposition en cycles disjoints d'une permutation, est ce que la somme des longueurs des cycles est égale au nombre d'éléments?

[pseudocode]

Salut
Une autre question si on a une décomposition en cycles disjoints d'une permutation, est ce que la somme des longueurs des cycles est égale au nombre d'éléments?

S'ils sont vraiment disjoints (pas de doublon) alors oui.