1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2017
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 21
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2017
    Messages : 2
    Points : 1
    Points
    1

    Par défaut Créer une liste des chemins possible à partir d'un arbre

    Bonjour tout le monde,
    J'essais de créer une liste des chemins possible à partir d'un arbre.

    J'ai trois objets : Séquence, Opération, Choix
    J'ai formé un arbre à partir de ces objets. Les feuilles sont des Opérations et Séquence et Choix sont des noeux qui peuvent contenir plusieurs branches.

    En entrée j'ai un arbre qui contient différents chemins, un chemin est appelé un processus. J'aimerai à partir de cet arbre obtenir tous les processus possibles sous forme d'une liste de liste.

    J'ai fait un schémas pour l'illustrer (en pièce jointe).

    Je voudrais faire une fonction qui passe de l'arbre à la liste de tous les processus possibles. J'ai commencé à réfléchir sur un algorithme récursif mais je ne m'en sors pas. Auriez vous déjà rencontré ce type de problème ? Si oui pourriez vous m'aider ?

    En attendant, j'ai écris un prgm qui me permet d'obtenir la liste [chauffage, [[laminage,roulage],ecrasage]] mais ce n'est pas une liste de processus.
    Images attachées Images attachées  

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

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 974
    Points : 6 971
    Points
    6 971

    Par défaut

    Bonjour

    L'algorithme récursif est une bonne idée.

    Tu crées une fonction définie comme suit :
    A chaque branche, tu fais la liste des branches filles.
    Pour chacune des filles, tu appelles la fonction en transmettant les ancêtres.
    Quand une branche n'a plus de fille, afficher la liste des ancêtres et le nom de la branche.

    Ainsi tu auras la liste de tous les chemins possibles.
    Comme il y a plusieurs chemins, tu as une liste (de chemins).
    Et comme une suite d'ancêtres est une liste, tu obtiens bien une liste de liste.
    Cette réponse vous apporte quelque chose ? 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
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2017
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 21
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2017
    Messages : 2
    Points : 1
    Points
    1

    Par défaut

    Merci pour ta réponse.

    Je ne comprends le bout "tu appelles la fonction en transmettant les ancêtres".

    Je comprends le principe, j'ai fait cet algorithme :


    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    def af(arbre,i):#renvoie une liste de processus, un processus peut etre une liste d'operations ou une unique operation (str)
     
        if isinstance(arbre,Sequence):
            return [af(arbre.Enfants[i],i) for i in range(len(arbre.Enfants))]
     
        if isinstance(arbre,Operation):
                return arbre.Nom
     
        if isinstance(arbre,Boucle):  #je considere que boucle n'a qu'un seul enfant
            for i in range(arbre.N):
                af(arbre.Enfants[0],0)
        if isinstance(arbre,Choix):
            return [af(arbre.Enfants[i],0) for i in range(len(arbre.Enfants)) ]

    Quand j'applique mon algorithme avec l'arbre "Sequence1" (sur la photo), j'obtient le résultat : [chauffage,[[laminage,roulage],ecrasage]]J'aimerai obtenir : [[chauffage,laminage],[chauffage,roulage],[chauffage,ecrasage]].

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

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 974
    Points : 6 971
    Points
    6 971

    Par défaut

    Le tout n'est pas cohérent. Ton arbre est mal dessiné.

    Les "choix" doivent être aux intersections.

    Et "chauffage" n'est pas commun à tous les parcours de ton arbre.
    Pourtant "chauffage" commence tous tes processus rêvés.
    Cette réponse vous apporte quelque chose ? 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++

  5. #5
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 622
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 622
    Points : 4 168
    Points
    4 168

    Par défaut

    salut

    si je comprend bien ta structure est de ce genre ?
    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
    18
    19
    BOCK0  [
    DEBUT SEQUENCE1
      BOCK1  [chauffage]
      BOCK2  [  
        TEST1 OUI
           BOCK3[ecrasage]
        TEST1 NON
          BOCK4
          [ TEST2  OUI
              laminage
           TEST2  NON
              roulage
            FIN TEST2
          ]
       FIN TEST1
      ]
    FIN SEQUENCE1
    ]
    Donc quand tu vas le lire et le mettre dans l'arbre tu devrais obtenir
    [chauffage,[ecrasage,[laminage,roulage]]]
    [SEQUENCE1,[TEST1,[TEST2]]]
    test processus doivent imperativement etre une liste même de 1 element mais
    en fait le processus doit être une feuille de ton arbre et pas un nœud

    pour obtenir ceci
    [[chauffage,laminage],[chauffage,roulage],[chauffage,ecrasage]]
    il te faut repérer la dernière feuille et vérifier que tu n'est pas déjà passé par celle-ci
    et remonter dans ton arbre jusqu’à la racine
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

Discussions similaires

  1. [Python 3.X] Créer une liste à partir d'un dictionnaire dont les clés sont des tuples !
    Par chouchou_beignet dans le forum Général Python
    Réponses: 2
    Dernier message: 15/09/2017, 12h29
  2. Réponses: 6
    Dernier message: 22/10/2015, 13h42
  3. afficher une Liste des videos a partir de SQLite
    Par radouanmst dans le forum Android
    Réponses: 0
    Dernier message: 24/08/2015, 13h25
  4. Créer une liste à partir des noms des feuilles
    Par BOU59000 dans le forum Macros et VBA Excel
    Réponses: 10
    Dernier message: 19/08/2008, 18h38
  5. Réponses: 2
    Dernier message: 22/09/2006, 09h29

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