Bonjour,

je cherche un algorithme efficace pour recoller des morceaux dans une sequence d'elements.
Par exemple prenons cette suite de caracteres:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
 
x1x1xx1x1x1x11xxxx
comment obtenir une suite consecutive de 7 fois '1' en effectuant le moins d'operations possibles,
sachant qu'une operation est une permutation de 2 caracteres?

une fois que ce probleme est resolu, je voudrais extraire, a partir d'une sequence semblable
mais beaucoup plus longue, la sous-sequence qui va générer le moins de permutations si on lui
applique l'énoncé d'au-dessus.
Exemple pour illustrer:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
 
const char *big_sequence[] = "xxxx1x1xx1x1x1x11xxxxxxxxxxxx11111x1";
const int count = 7;
char *sub_sequence = extract(big_sequence, '1', count);
printf("sous-sequence: %s\n", sub_sequence);
nous affichera
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
 
sous-sequence: 1xxxxxxxxxxxx11111x1
en effet dans cette sous-sequence il suffit de permuter le premier '1' avec le dernier 'x' pour obtenir la suite de 7 fois '1' qu'on cherchait et c'est la sous-sequence qui necessite le moins d'operations (une seule permutation)

par intuition je dirais que ca ressemble a un algo de tri/selection...
d'avance merci pour vos suggestions