Décomposition minimale d'une permutation 2
Salut à tous,
Je cherche à présent un algorithme qui permet de trouver la permutation minimale qui transforme la liste L1 en L2 puis donne la décomposition minimale de cette permutation en produit de "transpositions spéciales".
Je m'explique :
Étant donné qu'on manipule les listes il est possible de couper une sous-liste et de la recoller dans l'endroit voulu, c'est ça que j'appelle une
"transposition spéciale" car je ne connais pas comment l'appeler.
Voici un exemple simple pour bien comprendre (un tri) :
L1 : (2,2,2,2,2,2,0,0,0,0,0,0,0,0,0)
L2 : (0,0,0,0,0,0,0,0,0,2,2,2,2,2,2)
On a juste coupé le morceau (6,14) puis recollé en (0).
Ici le plus petit indice est 0
Donc l'unité élémentaire de la permutation est donnée sous forme :
((a, b), c), dans l'exemple ((6, 14), 0).
Merci d'avance.
Décomposition minimale d'une permutation 2
Citation:
Envoyé par
Champialex
Si je comprend bien le problème, tu cherche juste les plus longs motifs qui se répètent! ex :
L1(1.2.3.4.5.6.7.8.9.1.6)
L2(1.5.6.7.2.3.4.8.9.6.1)
au début t'as motifL2=1
ya deux 1 dans L1 => tu regarde le caractère après le premier : différent de celui de L2 => tu regarde le caractère après le deuxième : différent de celui de L2 => t'enregistre ce motifs et ces caractéristiques ((1,1),0) et tu le supprime de L1 et L2!
tu passe au motif suivant : motifL2=5
tu regarde le caractere apres le 5 : identique que celui dans L2
=> motifL2 = 5.6
tu regarde le caractere apres le 6 : identique que celui dans L2
=> motifL2=5.6.7
différent
=> enregistrement et suppression
....
Par contre fait gaffe, la décomposition n'est pas unique si tu n'as que ces contraintes...
ex si on avait pris :
L1(1.2.3.4.5.6.7.8.9.1.5)
L2(1.5.6.7.2.3.4.8.9.5.1)
au début il faut choisir entre mettre 1 tout seul et 5.6.7 ou 1.5 et 6.7
Merci pour la réponse, je crois qu'il faut mettre des contraintes qui permettent de choisir entre les décompositions, la première est sans doute : il faut choisir la décomposition la plus minimale, pour le reste on va voir :)
