sequence et permutations

Bonjour,

je cherche un algorithme efficace pour recoller des morceaux dans une sequence d'elements.
Par exemple prenons cette suite de caracteres:

Code:

---

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:

---

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:

---

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

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

regarde sur wiki.

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.

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:

---

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:

---

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]

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.

Citation:

---

Envoyé par 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.

---

Code:

---

1 2	111110000000101110111

---

Yes. ca marche.

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

Citation:

---

Envoyé par pseudocode

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

---

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