Discussion :

[b4u]

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

[Plorf]

Je te conseillerais tout d'abord de faire un bubble sort (tri à bulles).

regarde sur wiki.

[Trap D]

D'abord je ferais un parcours de la chaîne pour compter le nombre d'éléments de chaque catégorie et essayer de repérer où et avec quel élément on peut situer la chaîne la plus longue déjà constituée.
Je travaillerais ensuite avec 2 pointeurs l'un qui part du début de chaîne l'autre de la fin pour effectuer les échanges.
C'est juste une piste, il faut approfondir.

[b4u]

ben le bubble regroupera les '1' mais ne le fera pas en un minimum de permutations je crois. Or il faut garantir un nombre minimal de déplacements :/
je suis parti sur l'idée suivante:

Code :

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

1
2
3
4
5
6
7
8
 
1 - selectionner la portion qui comporte le maximum de '1'
2 - pour chaque element c de cette portion
       si (c != '1')
2a -      selectionner un element d = '1' en dehors de la portion
2b -      permuter c et d;
       fin si
     fin pour

en reprenant l'exemple du post initial ca donnerait:

Code :

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

1
2
3
4
5
x1x1xx1x1x1x11xxxx     // selection de la plus longue portion de '1'
xxx1xx111x1x11xxxx
xxxxxx11111x11xxxx
xxxxxx1111111xxxxx

ce qui nous ferait 3 permutations... maintenant la partie difficile etant de selectionner la portion et de choisir les bons candidats pour les permutations en un minimum de temps

[Edit: cross-post, Trap D tu as été plus rapide que moi merci je vais creuser ton idée]

[Jean-Marc.Bourguet]

Vous etes bien complique. On cherche est la suite de 7 caracteres contenant le plus de 1. Ensuite on l'etend pour avoir assez de 1.

[pseudocode]

Vous etes bien complique. On cherche est la suite de 7 caracteres contenant le plus de 1. Ensuite on l'etend pour avoir assez de 1.

Code :

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

1
2
111110000000101110111

Yes. ca marche.

(j'avais pas compris qu'on pouvait permuter deux elements non adjacents )

[Jean-Marc.Bourguet]

(j'avais pas compris qu'on pouvait permuter deux elements non adjacents )

Je l'ai compris grace a l'exemple. Jusque l'a j'avais suppose que ce n'est pas permis.