IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

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


Sujet :

Algorithmes et structures de données

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

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

    Informations forums :
    Inscription : Juillet 2004
    Messages : 2 725
    Points : 3 338
    Points
    3 338
    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 sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    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 apporte quelque chose ? Cliquez sur en bas à droite du message.

  3. #3
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    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 : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    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 sénior Avatar de disedorgue
    Homme Profil pro
    Ingénieur intégration
    Inscrit en
    Décembre 2012
    Messages
    4 266
    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 : 4 266
    Points : 12 681
    Points
    12 681
    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
    4 038
    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 : 4 038
    Points : 9 347
    Points
    9 347
    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 sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    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 apporte quelque chose ? Cliquez sur en bas à droite du message.

  7. #7
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    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 : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    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 sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    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 apporte quelque chose ? Cliquez sur en bas à droite du message.

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

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

    Informations forums :
    Inscription : Juillet 2004
    Messages : 2 725
    Points : 3 338
    Points
    3 338
    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 émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    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 : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    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 sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    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 apporte quelque chose ? Cliquez sur en bas à droite du message.

  12. #12
    Expert éminent sénior Avatar de disedorgue
    Homme Profil pro
    Ingénieur intégration
    Inscrit en
    Décembre 2012
    Messages
    4 266
    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 : 4 266
    Points : 12 681
    Points
    12 681
    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 725
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Sarthe (Pays de la Loire)

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

    Informations forums :
    Inscription : Juillet 2004
    Messages : 2 725
    Points : 3 338
    Points
    3 338
    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 sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    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 apporte quelque chose ? Cliquez sur en bas à droite du message.

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

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

    Informations forums :
    Inscription : Juillet 2004
    Messages : 2 725
    Points : 3 338
    Points
    3 338
    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 sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    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 apporte quelque chose ? Cliquez sur en bas à droite du message.

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

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

    Informations forums :
    Inscription : Juillet 2004
    Messages : 2 725
    Points : 3 338
    Points
    3 338
    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
    3 035
    Détails du profil
    Informations personnelles :
    Localisation : France

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

    Informations forums :
    Inscription : Novembre 2010
    Messages : 3 035
    Points : 8 400
    Points
    8 400
    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

Discussions similaires

  1. [MySQL] Récupération données (chaine de caractère) - Décomposition, concaténation ?
    Par yohan0262 dans le forum PHP & Base de données
    Réponses: 9
    Dernier message: 28/10/2009, 15h33
  2. Décomposition d'une chaine
    Par antitrust56 dans le forum Langage
    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 Langage
    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