1. #1
    Membre expert
    Homme Profil pro
    Architecte de système d'information
    Inscrit en
    juillet 2004
    Messages
    2 716
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Sarthe (Pays de la Loire)

    Informations professionnelles :
    Activité : Architecte de système d'information

    Informations forums :
    Inscription : juillet 2004
    Messages : 2 716
    Points : 3 319
    Points
    3 319

    Par défaut 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 :
    %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 :
    %tata%~%tutu%_%toto%~%titi%
    Donne :
    %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

    A savoir qu'il n'y a pas nécessairement de ET ou de OU, on peut avoir :
    %tata%
    %tata%_%toto%
    %tata%~%toto%
    %tata%~%tutu%_%titi%
    %tata%~%tutu%_%toto%
    %tata%~%tutu%_%toto%~%titi%
    Je me limite à deux OU et un ET pour le moment, le temps déjà d'arriver à traiter

    Merci d'avance pour votre aide sur l'algo
    Par pitié !!!! :Si vous ne savez pas faire cliquez ici !
    Citation Envoyé par Marc-L
    C'est dommage que parfois tu sois aussi lourd que tu as l'air intelligent…

  2. #2
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    2 744
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 744
    Points : 6 401
    Points
    6 401

    Par défaut

    Bonjour

    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.
    Cette réponse vous plaît ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  3. #3
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    550
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 550
    Points : 1 093
    Points
    1 093
    Billets dans le blog
    5

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

    Bonjour,

    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 Voir le message
    ... 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) .


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  4. #4
    Expert éminent Avatar de disedorgue
    Homme Profil pro
    Ingénieur intégration
    Inscrit en
    décembre 2012
    Messages
    2 581
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur intégration
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : décembre 2012
    Messages : 2 581
    Points : 7 178
    Points
    7 178

    Par défaut

    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% ?
    Cordialement.

  5. #5
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 661
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 661
    Points : 3 467
    Points
    3 467

    Par défaut

    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.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  6. #6
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    2 744
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 744
    Points : 6 401
    Points
    6 401

    Par défaut

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

    a+bc=(a+b)(a+c)
    Cette réponse vous plaît ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  7. #7
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    550
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 550
    Points : 1 093
    Points
    1 093
    Billets dans le blog
    5

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

    Citation Envoyé par Flodelarab Voir le message
    La noyade sera totale quand on rappellera que le OU est aussi distributif sur le ET que le ET sur le OU.

    a+bc=(a+b)(a+c)
    Là, je me sens en train de perdre pied (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 ?


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  8. #8
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    2 744
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 744
    Points : 6 401
    Points
    6 401

    Par défaut

    Citation Envoyé par wiwaxia Voir le message
    A-t-on alerté les secouristes ?
    George Boole et Claude Shannon ? J'ai une mauvaise nouvelle ... Ils sont morts.

    Ils nous ont laissé un parchemin cryptique qui semble lister les règles de simplification qui s'appliquent dans cette algèbre.
    Cette réponse vous plaît ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  9. #9
    Membre expert
    Homme Profil pro
    Architecte de système d'information
    Inscrit en
    juillet 2004
    Messages
    2 716
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Sarthe (Pays de la Loire)

    Informations professionnelles :
    Activité : Architecte de système d'information

    Informations forums :
    Inscription : juillet 2004
    Messages : 2 716
    Points : 3 319
    Points
    3 319

    Par défaut

    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
    Par pitié !!!! :Si vous ne savez pas faire cliquez ici !
    Citation Envoyé par Marc-L
    C'est dommage que parfois tu sois aussi lourd que tu as l'air intelligent…

  10. #10
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    550
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 550
    Points : 1 093
    Points
    1 093
    Billets dans le blog
    5

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

    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 Voir le message
    ... %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 Voir le message
    ... 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 ?


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  11. #11
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    2 744
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 744
    Points : 6 401
    Points
    6 401

    Par défaut

    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.
    Cette réponse vous plaît ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  12. #12
    Expert éminent Avatar de disedorgue
    Homme Profil pro
    Ingénieur intégration
    Inscrit en
    décembre 2012
    Messages
    2 581
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur intégration
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : décembre 2012
    Messages : 2 581
    Points : 7 178
    Points
    7 178

    Par défaut

    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 ?
    Cordialement.

  13. #13
    Membre expert
    Homme Profil pro
    Architecte de système d'information
    Inscrit en
    juillet 2004
    Messages
    2 716
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Sarthe (Pays de la Loire)

    Informations professionnelles :
    Activité : Architecte de système d'information

    Informations forums :
    Inscription : juillet 2004
    Messages : 2 716
    Points : 3 319
    Points
    3 319

    Par défaut

    @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

    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 !
    Par pitié !!!! :Si vous ne savez pas faire cliquez ici !
    Citation Envoyé par Marc-L
    C'est dommage que parfois tu sois aussi lourd que tu as l'air intelligent…

  14. #14
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    2 744
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 744
    Points : 6 401
    Points
    6 401

    Par défaut

    Ce serait plus simple si on connaissait le nombre d'ensembles. On ferait juste des boucles "for" imbriquées.
    Cette réponse vous plaît ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  15. #15
    Membre expert
    Homme Profil pro
    Architecte de système d'information
    Inscrit en
    juillet 2004
    Messages
    2 716
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Sarthe (Pays de la Loire)

    Informations professionnelles :
    Activité : Architecte de système d'information

    Informations forums :
    Inscription : juillet 2004
    Messages : 2 716
    Points : 3 319
    Points
    3 319

    Par défaut

    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
    Mais me limiter au départ à 3 ou 4 niveau...

    J'aime quand c'est dynamique
    Par pitié !!!! :Si vous ne savez pas faire cliquez ici !
    Citation Envoyé par Marc-L
    C'est dommage que parfois tu sois aussi lourd que tu as l'air intelligent…

  16. #16
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    2 744
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 744
    Points : 6 401
    Points
    6 401

    Par défaut

    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    grep 'motif1\|motif2' fichier |grep 'motif3\|motif4'
    Est-ce indiscret de demander ton but ?
    Cette réponse vous plaît ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  17. #17
    Membre expert
    Homme Profil pro
    Architecte de système d'information
    Inscrit en
    juillet 2004
    Messages
    2 716
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Sarthe (Pays de la Loire)

    Informations professionnelles :
    Activité : Architecte de système d'information

    Informations forums :
    Inscription : juillet 2004
    Messages : 2 716
    Points : 3 319
    Points
    3 319

    Par défaut

    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é
    Par pitié !!!! :Si vous ne savez pas faire cliquez ici !
    Citation Envoyé par Marc-L
    C'est dommage que parfois tu sois aussi lourd que tu as l'air intelligent…

  18. #18
    Expert éminent Avatar de BufferBob
    Profil pro
    responsable R&D vidage de truites
    Inscrit en
    novembre 2010
    Messages
    2 424
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : responsable R&D vidage de truites

    Informations forums :
    Inscription : novembre 2010
    Messages : 2 424
    Points : 6 485
    Points
    6 485

    Par défaut

    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
    Avant donc que d'écrire, apprenez à penser.
    Selon que notre idée est plus ou moins obscure, l'expression la suit, ou moins nette, ou plus pure.
    Ce que l'on conçoit bien s'énonce clairement, et les mots pour le dire arrivent aisément.
                                                        - Nicolas Boileau, L'Art poétique

Discussions similaires

  1. Réponses: 9
    Dernier message: 28/10/2009, 15h33
  2. Décomposition d'une chaine
    Par antitrust56 dans le forum Fonctions
    Réponses: 2
    Dernier message: 24/02/2009, 11h10
  3. décomposition de chaine bloquée
    Par moi5252 dans le forum Excel
    Réponses: 4
    Dernier message: 23/03/2008, 19h15
  4. Décomposition de chaine de caractères
    Par Badaboumpanpan dans le forum Fonctions
    Réponses: 6
    Dernier message: 21/06/2007, 12h11
  5. Décomposition d'une chaine de caractères
    Par stephdiplo150 dans le forum C
    Réponses: 3
    Dernier message: 04/03/2004, 23h50

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo