Discussion :

[Bobez42]

Bonjour à tous,

Je sèche bêtement devant un problème qui pourtant me semble assez simple : je cherche à écrire une fonction qui prend une chaîne s et un entier n en paramètre, et qui m'affiche / me stocke l'ensemble des sous-séquences de s de taille au plus n.

Par exemple :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
sous_sequences("abca",3);
a
ab
ac
aa
abc
aba
aca
b
bc
ba
bca
c
ca
a

(l'ordre d'affichage n'est pas important)

Des idées ?
Merci beaucoup de votre aide !

[Scorpi0]

Calcul le nombre de caractère de ta chaine en entrée.
Après, une double boucle sur le nombre de char de ta chaine en entrée, et sur le deuxième argument devrait suffire.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
sous_sequences(chaine, entier)
 
  pour i de 0 à taille(chaine) - 1
    pour j de 0 à entier - 1
      si chaine[i+j] est valide
        afficher chaine[i,i+j]
      fin si
    fin pour
  fin pour
 
fin sous_sequences

[Bobez42]

Merci de ta réponse, mais attention, je ne cherche pas seulement les sous-séquences contiguës mais l'ensemble des sous-séquences (c'est-à-dire qu'il peut y avoir des trous, cf. l'exemple dans mon premier post).

[Scorpi0]

Oups, effectivement ça me semblait trop simple ^^
On reprend donc :

Code :

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

1
2
3
4
5
6
7
8
9
10
sous_sequences(chaine, entier)
 
   pour j de 0 à entier - 1
 
      /* Le problème revient ici a extraire les sous séquences de taille j de la chaine */
      sous_sequences2(j , chaine)
 
  fin pour
 
fin sous_sequences

Le problème se résume maintenant a extraire les combinaisons de j élément parmi taille(chaine) élément, genre un Cnp (CF wikipedia).
Et la je pense que soit il existe des bibliothèques, soit tu doit coder ton propre générateur de combinaison, le plus probable étant un algo récursif je pense.

Tu en tire une suite de j nombre compris entre 0 et taille[chaine], genre 1, 3, 5 si j=3, il ne te reste plu qu'a afficher chaine[1]||chaine[3]||chaine[5].

Bon courage ^^

[Bobez42]

Merci pour ta réponse. J'ai également pensé à réduire le problème comme tu l'as fait. Et cela revient en effet à trouver toutes les suites d'entiers strictement croissantes de taille n (avec chaque entier compris entre 0 et la taille de la chaîne).

Cela dit, j'ai essayé de réfléchir à une manière de coder cela et j'avoue que cela ne me vient pas Pour un n donné, c'est simple, il suffit d'imbriquer n boucles, mais je n'arrive pas à trouver la généralisation...

Si quelqu'un connait l'existence d'une bibliothèque C capable de faire cela...

[Bobez42]

J'ai trouvé mon bonheur dans le post suivant :
http://www.developpez.net/forums/sho...d.php?t=429282

Adapté en C, cela donne :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void partition (int index, int n, int p, int liste[]) {
  int start = 0;
  int i;
  if (index < p) {
    if (index > 0)
      start = liste[index-1]+1;
    for (i = start; i < n; i++) {
	  liste[index]=i;
	  partition(index+1,n,p,liste);
    }
  } else {
    for (i = 0; i < p; i++) {
      printf("%d ",liste[i]);
    }
    printf("\n");
  }
}

Et un exemple d'appel :

Code :

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

1
2
int liste[3];
partition(0,5,3,liste);

Comme quoi, c'était pas franchement sorcier
Merci encore à toi Scorpi0 d'avoir pris le temps de me répondre !