Discussion :

[tiboel]

Bonjour,

Dans le cadre du développement d'un moteur de recherche, je chercher à décomposer la chaine de requêtes en sous élément de la manière suivante.

Si q="A B" par exemple l'ago doit renvoyer
1 - "A B"
2 -"A", "B"

Si q="A B C" par exemple, l'agorithmes doit me renvoyer :
1-"A B C"
2 - "A B", "C"
3 -"A", "B C"
4- "A","B","C"

Si q="A B C D" par exemple l'ago doit me renvoyer
1-"A B C D"
2-"A B C","D"
3-"A", "B C D"
4-"A B","CD"
5- "A", "BC", "D"
....


Je vois bien que ça avoir avec les arrangements ou quelque chose comme ça mais impossible de trouver la règle pour me renvoyer ça quelque soit la chaine q, si vous avez des idées, je suis plus que preneur !!!!

Merci

Thibaud

[ToTo13]

Bonjour,

sous la forme dont tu l'as écrit, un séparateur évident dans ta chaine de caractère est l'espace.
Tu peux peut etre essayer de décomposer ta phrase dans un tableau de mots (chaine de caractères).
Ensuite, il te restera à faire les combinaisons que tu souhaites (strcat power).

Thibault (mais c'est mon nom de famille )

[tiboel]

Bonjour Monsieur Thibault

Je l'ai mis sous forme de chaine pour simplifier mais ma question ce n'est pas comment gérer les chaines de caractère, c'est trouver les combinaisons. On pourrait résonner tout simplement avec des nombres. Je cherche donc la fonction qui au nombre 123 associe

123
12-3
1-23
1-2-3

[ToTo13]

Alors,
si les - représentent un espaces, ou tout autre caractère et que le longueur de ta chaine soit 3 ( 123 ).

Code :

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

1
2
3
4
 
pour i de 1 à taille-1 // gère le nombre de trous
     récursivité pour placer les espaces (ou trous) à tout les endroits possible sauf au début ou à la fin en ajoutant la condition que deux blancs ne peuvent se toucher
     Donc autant d'appels que de trous

c'est un algo comme ca qu'il faut faire, la récursivité semble inévitable.

Bon courage.

[BugFactory]

On a un nombre N d'éléments, qui peuvent être ou non séparés par un blanc.
On peut repésenter l'état du système par un nombre binaire X de N-1 chiffres. Un 1 repésente un blanc, un 0 pas de blanc. La position de chaque chiffre correspond à celle d'un blanc.

Par exemple pour N = 4
000 --> ABCD
001 --> ABC D
010 --> AB CD
011 --> AB C D
100 --> A BCD
101 --> A BC D
110 --> A B CD
111 --> A B C D

Le problème est que l'on considère alternativement X comme un nombre binaire puis comme un motif, ce qui n'est pas orthodoxe. En revanche, l'implémentation est simple : X est un entier, dans les deux cas.

[Edit] Oops! Je viens de m'apercevoir que vous désirez d'abord les solutions à un trou, puis à deux troux, etc... Oubliez ce qui précède, je vais trouver mieux.[/Edit]

[BugFactory]

Deux solutions.
A. Réutiliser la proposition précédente, en comptant le nombre de blancs à chaque fois.

B. Faire une boucle sur le nombre de blancs que l'on veut.
A chaque itération, placer les blancs à droite, puis utiliser des boucles pour les dépacer vers la gauche. Je soupçonne cette solution dêtre compliquée.
000111
001011
001101
001110
010011
etc...
pour 3 blancs sur six positions doit déjà être long à coder. Alors m blancs sur N-1 postions...

[Trap D]

Personnellement, j'utiliserai une file avec un marqueur de fin de file

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
// initialisation de l'algo
enfiler la liste formée de la première lettre
enfiler le marqueur de fin de file
 
// algo proprement dit
tant que la liste des lettres n'est pas vide faire
  lettre <- prochaine_lettre
  liste <- defiler un élement de la file
  tant que  liste <> marqueur de fin de file faire
    nouvelle liste <- ajouter la lettre à la liste séparé par une virgule
    enfiler la nouvelle liste 
    nouvelle liste <- la liste + la lettre collée
    enfiler la nouvelle liste
  fin tant que
  enfiler le marqueur de fin de file
  liste <- defiler un élement de la file
fin tant que

[tiboel]

Merci BugFactory (et les autres )

Ta méthode est propre, rapide et surtout trés belle. Je l'ai implémenté en deux lignes en php. Bravo !!

Thibaud