Décomposition et assemblage de chaines par itération avec ET et OU

Bonjour à tous,

Je cherche à décomposer puis à recomposer des chaines de caractères en itérant l'ensemble.

Au départ j'ai une chaîne complexe exemple :

Citation:

---

%tata%~%tutu%_%toto%~%titi%

---

La chaîne est forcément composé au minimum d'un seul %element%
La séparation ~ représente un OU et la séparation _ représente un ET

Je souhaite décomposer la chaîne de base pour la recomposer comme ceci :

Citation:

---

%tata%~%tutu%_%toto%~%titi%

---

Donne :

Citation:

---

%tata%_%toto%
%tata%_%titi%
%tutu%_%toto%
%tutu%_%titi%

---

J'ai essayé plusieurs idées sans succès.
Principalement des boucles FOR ou WHILE avec un système de compteurs, mais je me perds vite dans la descente des enfants.
J'essaye d'éviter la récursivité, j'aurais aime uniquement de l'itératif si cela est possible.

Mon principe au départ étant de spliter les ET puis d'itérer le résultat et de spliter les et d'enchainer l'itération mais la c'est l'anarchie :calim2:

A savoir qu'il n'y a pas nécessairement de ET ou de OU, on peut avoir :

Citation:

---

%tata%

---

Citation:

---

%tata%_%toto%

---

Citation:

---

%tata%~%toto%

---

Citation:

---

%tata%~%tutu%_%titi%

---

Citation:

---

%tata%~%tutu%_%toto%

---

Citation:

---

%tata%~%tutu%_%toto%~%titi%

---

Je me limite à deux OU et un ET pour le moment, le temps déjà d'arriver à traiter :D

Merci d'avance pour votre aide sur l'algo ;)

Bonjour :coucou:

Dit simplement, tu veux distribuer un "et" sur un "ou".

Je suis un peu perplexe de ne voir apparaître ni inverse/opposé/complément (appelle-le comme tu veux), ni parenthèses dans ton expression.

a+bc+d ne demande aucune distribution.
Alors que (a+b)(c+d) en demande une qui deviendra finalement par ac+ad+bc+bd.
L'énoncé que tu poses est du premier cas et non du second.

Dans le cas général, si tu as 2 facteurs de n et m termes, alors le résultat sera une somme (ou) de m*n produits (et).
Donc itération sur m et sous-itération sur n.
Facile.

Bonjour, :D

Je crois que l'absence de parenthèses - déjà pointée par Flodelarab - constitue dès le départ un obstacle insurmontable, parce qu'elle exclut toute transformation de la chaîne.

La décomposition en éléments simples que tu évoques

Citation:

---

Envoyé par cerede2000

... Je souhaite décomposer la chaîne de base pour la recomposer comme ceci :
%tata%~%tutu%_%toto%~%titi%
Donne :
%tata%_%toto%
%tata%_%titi%
%tutu%_%toto%
%tutu%_%titi%
J'ai essayé plusieurs idées sans succès ...

---

suppose implicitement la distributivité du 'ET' (_) sur le 'OU' (~), et que l'on parte obligatoirement de l'expression (abrégée pour une meilleure lisibilité)
(A~B)_(C~D) = (A_C)~(A_D)~(B_C)~(B_D) = A_C~A_D~B_C~B_D
compte tenu de la préséance du premier opérateur (_) sur le second.

Pour la même raison, la chaîne initialement proposée %tata%~%tutu%_%toto%~%titi% ne permet qu'une seule interprétation:
%tata%~(%tutu%_%toto%)~%titi% ,
et ne peut être ni décomposée, ni simplifiée.

Plus grave encore, l'absence de parenthèses exclut une expression telle que (A~B)_C ,
la séquence de trois termes A~B_C ne pouvant conduire qu'à A~(B_C) .

Bonjour,

C'est vrai que sans les parenthèses, ton exemple n'est pas assez explicite.

Par exemple, que donnerait: %toto%~%tata%_%tutu%~%titi%_%fifi%~%fafa% ?

Pour la facilité des dialogues, je pense que ce serait plus simple d'utiliser : toto + tata * tutu + titi * fifi + fafa
plutôt que : %toto%~%tata%_%tutu%~%titi%_%fifi%~%fafa%

Une fois que tout sera clair avec les symboles usuels, retraduire tout avec les symboles ~ et _ au lieu de + et * , ça devrait être simple.

Sauf si le but du jeu, c'est de se noyer le plus vite possible.

La noyade sera totale quand on rappellera que le OU est aussi distributif sur le ET que le ET sur le OU. :lol:

a+bc=(a+b)(a+c)

Citation:

---

Envoyé par Flodelarab

La noyade sera totale quand on rappellera que le OU est aussi distributif sur le ET que le ET sur le OU. :lol:

a+bc=(a+b)(a+c)

---

Là, je me sens en train de perdre pied :help: (AetB)ou(CetD) = (AouC)et(AouD)et(BouC)et(BouD) ?

Soit encore, pour tenter de ne pas boire la tasse:
(A*B)+(C*D) = (A+C)*(A+D)*(B+C)*(B+D) et comme il n'est pas question de lutter contre le courant
= ((A+C)*(A+D))*((B+C)*(B+D)) = (A*A+A*D+C*A+C*D)*(B*B+B*D+C*B+C*D) = ... A-t-on alerté les secouristes ?

Citation:

---

Envoyé par wiwaxia

A-t-on alerté les secouristes ?

---

:mouarf: George Boole et Claude Shannon ? J'ai une mauvaise nouvelle ... Ils sont morts. :ouin:

Ils nous ont laissé un parchemin cryptique qui semble lister les règles de simplification qui s'appliquent dans cette algèbre.:hola:

Bonjour à tous,

Je vois que le sujet fais débat :)

Je ne peux tout simplement pas utilisé de + et de * car les chaines peuvent en contenir... malheureusement !

Alors qu'il n'y aura pas de ~ et de _

Pour la question de parenthèses en effet, mais je m'en passe avec un moyen simple, c'est que le traitement des chaines sera fait via une regex.
Celle-ci capture d'abords les ET (_) pour ensuite appliquer la distribution des OU (~)

Donc lorsque une chaine se présente %truc%_%bidule%~%machin%_%muche%
La regex (un split est aussi largement suffisant :) ) extrait droite et gauche de chaque ET
Puis extrait chaque OU des morceaux précédents.

%truc%_%bidule%~%machin%_%muche% donne donc :
%truc%
ET
%bidule%~%machin%
ET
%muche%

Puis :
%truc%
ET
%bidule% OU %machin%
ET
%muche%

Ce qui au final est attendu :
%truc% ET %bidule% ET %muche%
OU
%truc% ET %machin% ET %muche%


Et dans le cas de @disedorgue %toto%~%tata%_%tutu%~%titi%_%fifi%~%fafa%
toto ET tutu ET fifi
toto ET tutu ET fafa
toto ET titi ET fifi
toto ET titi ET fafa
tata ET tutu ET fifi
tata ET tutu ET fafa
tata ET titi ET fifi
tata ET toto ET fafa

1°) Cela paraît conforme aux règles du calcul algébrique, avec la correspondance déjà repérée: '~' = 'OU' = '+' ; '_' = 'ET' = '*' :

Citation:

---

Envoyé par cerede2000

... %truc%_%bidule%~%machin%_%muche% donne donc :
%truc%
ET
%bidule%~%machin%
ET
%muche%

Puis :
%truc%
ET
%bidule% OU %machin%
ET
%muche%

Ce qui au final est attendu :
%truc% ET %bidule% ET %muche%
OU
%truc% ET %machin% ET %muche% ...

---

Cependant l'augmentation du nombre de termes (qui passe de 4 à 6) implique l'action simultanée d'un opérateur sur plusieurs termes et sa distributivité, donc la présence implicite d'une paire de parenthèses délimitant un groupe d'au moins deux termes: la traduction simple de ce qui précède donne:
A*(B+C)*D = A*B*D + A*C*D .

2°) La représentation des opérateurs est en effet sans conséquence:

Citation:

---

Envoyé par cerede2000

... Je ne peux tout simplement pas utiliser de + et de * car les chaines peuvent en contenir... malheureusement !

Alors qu'il n'y aura pas de ~ et de _

Pour la question de parenthèses en effet, mais je m'en passe avec un moyen simple, c'est que le traitement des chaines sera fait via une regex.
Celle-ci capture d'abord les ET (_) pour ensuite appliquer la distribution des OU (~) ...

---

Mais c'est bien ici l'épineuse question: ta démarche a pratiquement pour effet d'imposer la préséance du 'OU' = '~' sur l'autre opérateur, contrairement à ce que tu en dis - ou ce que je crois en comprendre.
Je n'ai rien à priori contre un développement de chaînes de caractères, selon des règles arbitraires; mais cela ne me paraît pas clair.

Qu'obtiendra-t-on par exemple pour: A*B+C*D+E*F , ou: A*B+C+D*E ?
Et quelle est la difficulté que tu rencontres ?

Citation:

---

Qu'obtiendra-t-on par exemple pour: A*B+C*D+E*F , ou: A*B+C+D*E ?

---

ABDF
ABEF
ACDF
ACEF

et

ABD
ABE
ACD
ACE


En fait, cerede2000 veut juste faire un produit cartésien d'ensembles séparés par _ dont chaque élément est séparé par ~.
L'algorithme est la distribution. comme indiquée dès le début.

@cerede2000: Tu ne vois pas ?

1. Chaque ensemble a un compteur pour dire quel élément est désigné. Commence par le premier ensemble.
2. Puis tu passes à l'ensemble suivant.
3. Quand il n'y a pas d'ensemble suivant, tu affiches tous les éléments désignés (autant que d'ensembles).
4. Puis le compteur de l'ensemble actif augmente.
5. S'il dépasse le nombre d'éléments de l'ensemble, tu remets le compteur au minimum et tu remontes d'un ensemble, et recommence à l'étape 4.
6. L'algorithme s'arrête quand tu est remonté plus haut que ton premier ensemble, car cela signifie que tu as fait tous les cas possibles. Sinon aller à l'étape 2.

Bon, tu as l'algorithme générique maintenant, mais une question qui peut avoir son importance:
Tu fais ton développement avec quel langage ?

@Flodelarab : Yes !
C'est bien ce que j'avais imaginé en fait lol.

Mais je m'était bêtement dit : On peut surement faire plus simple ou plus efficient :mouarf:

Donc c'est partit pour un système de multi-compteur avec vérification à chaque fois du max par compteur pour repartir de 0 et incrémenter le suivant :)

0-0-0
0-0-1
0-0-2
0-0-3
0-1-0
0-1-1
0-1-2
0-1-3
........
n-n-n

Ca sera du Powershell, aucun soucis pour la réalisation ;)

Merci à vous !

Ce serait plus simple si on connaissait le nombre d'ensembles. On ferait juste des boucles "for" imbriquées.

On ne le connais pas forcément, c'est l'utilisateur qui fais ses filtres comme il le désire.

Alors il ne va pas en faire 50 non plus :aie:
Mais me limiter au départ à 3 ou 4 niveau...

J'aime quand c'est dynamique :mrgreen:

Nous sommes dans le forum algorithme. Donc le système n'intervient pas. Mais un linuxien fait ton filtre en une seule ligne de commande sur un fichier.

(motif1 ou motif2) et (motif3 ou motif4)

Code:

---

grep 'motif1\|motif2' fichier |grep 'motif3\|motif4'

---

Est-ce indiscret de demander ton but ?

Non pas du tout indiscret :)

Le but final est le filtrage d'application depuis MDT de Microsoft.

J'ai des variables qui sont défini et une liste d'application.

Et je filtre les applications depuis leur titre avec le système indiqué :)

salut,

sur un plan plus pratique que matheux, il me semble que dans ce genre de situation on a coutume de recourir à du recursive descent parsing, beaucoup de libs existent par ailleurs pour simplifier l'écriture d'un tel parser