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

  1. #1
    Membre habitué
    Homme Profil pro
    Directeur des systèmes d'information
    Inscrit en
    mars 2002
    Messages
    129
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France, Lot et Garonne (Aquitaine)

    Informations professionnelles :
    Activité : Directeur des systèmes d'information
    Secteur : Conseil

    Informations forums :
    Inscription : mars 2002
    Messages : 129
    Points : 129
    Points
    129

    Par défaut Combinaisons possibles, récursivité

    Bonjour.
    Ca fait bien longtemps que j'ai appris à développer mais j'ai complètement oublié comment on fait de la récursivité. J'ai un problème pour trouver toutes les combinaisons possibles dans un tableau. Je m'explique.

    J'ai un tableau de x cases sur y.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    A1   B1   C1
    A2   B2   C2
    A3   B3   C3
    Pour l'exemple je fais un tableau de 3X3


    Je cherche à avoir dans un fichier toutes les combinaisons possibles des valeurs des 3 colonnes. Sans permutations. Donc le résultat doit être:

    A1B1C1
    A1B1C2
    A1B1C3
    A1B2C1
    A1B2C2
    A1B2C3
    A1B3C1
    A1B3C2
    A1B3C3
    A2B1C1
    A2B1C2
    A2B1C3
    A2B2C1
    A2B2C2
    A2B2C3

    Etc... Jusqu'à A3B3C3

    Je n'arrive pas à trouver par quel bout le prendre!!! Ca ne doit pas être difficile mais je n'arrive plus à réfléchir... Ca doit être l'âge et le manque de pratique...


    Merci

  2. #2
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    24 495
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 24 495
    Points : 162 524
    Points
    162 524

    Par défaut



    Un des principes pour construire une fonction récursive, c'est d'effectuer un tout petit bout de travail, puis déléguer à un appel récursif. Ici, tu pourrais avoir un appel récursif sur les deux dernières colonnes, tu traites le cas d'une seule colonne : pour toutes les combinaisons possibles des deux dernières colonnes, tu ajoutes les valeurs nécessaires de la première. Il faut définir un cas de base : si tu as zéro colonnes à traiter, tu n'as qu'une seule possibilité, une liste vide.
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

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

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 778
    Points : 9 173
    Points
    9 173

    Par défaut

    Bonjour

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    Pour chaque case de la colonne, traiter la colonne suivante.
    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++

  4. #4
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 484
    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 : 2 484
    Points : 5 330
    Points
    5 330

    Par défaut

    Ici, si on veut un truc qui traite 26 lettres, et 9 chiffres :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    alphabet = "ABCDEFGHIJKLMNOPQRSTUV"
    Resultat = ""
    rang_en_cours = 0
     
    traite ( alphabet , resultat , rang_en_cours )
    Et la fonction traite sera celle ci :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
     
    procedure traite ( alph, resu, rg)
     
    si rg = 26 alors 
        print ( resu )
        retour
    sinon
       pour i = 1 a  9
            res = resu ||  ' ' || milieu( alph,i) || i
            traite ( alph, res, rg+1 )
       fin
    fin
    Reste à traduire ce pseudo-code dans un vrai langage, à l'adapter, à le tester ... mais c'est une base.
    Ici 26 caractères, 9 options à chaque caractère, le nombre de combinaisons va être énorme, et ce ne serait pas raisonnable de l'exécuter tel quel !

    Le principe d'une fonction récursive, c'est qu'on a une fonction ffff , avec souvent 2 paramètres (un des paramètres compte les étapes déjà effectuées ou restant à effectuer). Et dans le corps de cette fonction ffff, on fait un appel à ffff !
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  5. #5
    Membre habitué
    Homme Profil pro
    Directeur des systèmes d'information
    Inscrit en
    mars 2002
    Messages
    129
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France, Lot et Garonne (Aquitaine)

    Informations professionnelles :
    Activité : Directeur des systèmes d'information
    Secteur : Conseil

    Informations forums :
    Inscription : mars 2002
    Messages : 129
    Points : 129
    Points
    129

    Par défaut Merci...

    Je vais maintenant essayer de finir... Une fois résolu je cocherai "résolu"

    Merci

  6. #6
    Membre habitué
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    186
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 186
    Points : 125
    Points
    125

    Par défaut

    Sinon, tu peux aller pécher des algos de combinatoire sur le net et les déchiffrer, si tu bute sur de la syntaxe, tu peux revenir demander des explics spécifiques(en nommant le langage (bien qu'on puisse le deviner) (c'est ce que je fais en général quand je cherche un algo particulier).

  7. #7
    Membre habitué
    Homme Profil pro
    Directeur des systèmes d'information
    Inscrit en
    mars 2002
    Messages
    129
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France, Lot et Garonne (Aquitaine)

    Informations professionnelles :
    Activité : Directeur des systèmes d'information
    Secteur : Conseil

    Informations forums :
    Inscription : mars 2002
    Messages : 129
    Points : 129
    Points
    129

    Par défaut J'arrive pas!

    Aïe... Je n'y arrive pas... Je vous colle ici où j'en suis. Je crois qu'il ne manque pas grand chose mais le résultat n'est pas bon. C'est en Pascal.

    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
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    procedure TForm_campagne.cxButton2Click(Sender: TObject);var
    ligneInit:integer;
    Chaine:String;
    begin
        cxMemo1.Lines.Clear;
     
     
        for ligneInit := 0 to Grid.DataController.RecordCount-1 do
        begin
             chaine:='';
             Traiter(LigneInit,0,Chaine);
     
     
        end;
    end;
     
     
    procedure TForm_campagne.Traiter(ligne, colonne: integer; Var Chaine:String);
    var
    valeur:String;
    i: Integer;
    begin
         if Grid.DataController.GetValue(ligne,colonne)<>Null then
         begin
             Valeur:=Grid.DataController.GetValue(ligne,colonne);
             if valeur<>'' then
             begin
                Chaine:=Chaine+Valeur;
                if colonne+1<Grid.ItemCount-1 then
                  Traiter(ligne,colonne+1,chaine)
                else
                begin
                    if (Valeur<>'') and (chaine<>'') then
                    begin
                      cxmemo1.Lines.Add(chaine);
                      chaine:='';
                    end;
                    //if ligne+1<Grid.datacontroller.RecordCount-1 then
                    //    Traiter(ligne+1,colonne,chaine);
                end;
             end;
     
     
         end
         else
         begin
           if Chaine<>'' then
           begin
              cxmemo1.Lines.Add(chaine);
              chaine:='';
           end;
     
     
         end;
     
     
    end;

  8. #8
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 484
    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 : 2 484
    Points : 5 330
    Points
    5 330

    Par défaut

    En ligne 8 de ton code, tu as une boucle for. for ligneInit := 0 to Grid.DataController.RecordCount-1 doPourquoi pas. Je pense que ce n'est pas indispensable, mais dans certains cas, ça simplifie bien les choses.

    Mais, il faut également une boucle for dans la procédure Traiter(). Là, avec la version actuelle, si tu pars d'un élément de la ligne 10 colonne 1, tu vas l'associer avec ligne 10 colonne 2, ligne 10, colonne 3... Il n'y a aucune instruction qui modifie la variable ligne.

    Je propose ça :

    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
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    procedure TForm_campagne.cxButton2Click(Sender: TObject);var
    ligneInit:integer;
    Chaine:String;
    begin
        cxMemo1.Lines.Clear;
     
             chaine:='';
             Traiter(0,Chaine);
     
    end;
     
    procedure TForm_campagne.Traiter(  colonne: integer; Var Chaine:String);
    var
    ligne:integer;
    valeur:String;
    i: Integer;
    begin
       for ligne := 0 to Grid.DataController.RecordCount-1 do
       begin
         if Grid.DataController.GetValue(ligne,colonne)<>Null then
         begin
             Valeur:=Grid.DataController.GetValue(ligne,colonne);
             if valeur<>'' then
             begin
                Chaine:=Chaine+Valeur;
                if colonne+1<Grid.ItemCount-1 then
                  Traiter(ligne,colonne+1,chaine)
                else
                begin
                    if (Valeur<>'') and (chaine<>'') then
                    begin
                      cxmemo1.Lines.Add(chaine);
                      chaine:='';
                    end;
                    //if ligne+1<Grid.datacontroller.RecordCount-1 then
                    //    Traiter(ligne+1,colonne,chaine);
                end;
             end;
     
         end
         else
         begin
           if Chaine<>'' then
           begin
              cxmemo1.Lines.Add(chaine);
              chaine:='';
           end;
     
         end;
      end ;
     
    end;
    Je ne suis pas 100% convaincu. Si ça marche, tant mieux, mais si ça ne marche pas, il faut probablement ENLEVER des trucs.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  9. #9
    Membre habitué
    Homme Profil pro
    Directeur des systèmes d'information
    Inscrit en
    mars 2002
    Messages
    129
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France, Lot et Garonne (Aquitaine)

    Informations professionnelles :
    Activité : Directeur des systèmes d'information
    Secteur : Conseil

    Informations forums :
    Inscription : mars 2002
    Messages : 129
    Points : 129
    Points
    129

    Par défaut Mal à la tête...

    Merci de ton code. Le résultat donne ça, avec cet algo. J'ai l'impression que la récursivité s'applique mal... Il faudrait "revenir" en colonne 0 mais je ne sais pas comment.

    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
    20
    21
    22
    23
    24
    25
    26
    a1B1C1C2
    C3
    B2C1
    C2
    C3
    B3C1
    C2
    C3
    a2B1C1
    C2
    C3
    B2C1
    C2
    C3
    B3C1
    C2
    C3
    a3B1C1
    C2
    C3
    B2C1
    C2
    C3
    B3C1
    C2
    C3

  10. #10
    Membre habitué
    Homme Profil pro
    Directeur des systèmes d'information
    Inscrit en
    mars 2002
    Messages
    129
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France, Lot et Garonne (Aquitaine)

    Informations professionnelles :
    Activité : Directeur des systèmes d'information
    Secteur : Conseil

    Informations forums :
    Inscription : mars 2002
    Messages : 129
    Points : 129
    Points
    129

    Par défaut Pas de boucle dans la fonction récursive?

    Je pense qu'il ne faut pas de boucle dans la fonction récursive. En effet, on doit faire une boucle seulement sur les lignes de la première colonne. non?
    De plus je me demande si il ne faut pas DEUX fonctions pour que ça marche...

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

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 778
    Points : 9 173
    Points
    9 173

    Par défaut

    Vos codes m'ont l'air bien compliqués.

    Voici un exemple simple de script python en récursion :
    Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    #!/usr/bin/python
     
    def combi(col,maxcol,maxrow,historique):
        if  (col>maxcol) :
            print historique
        else :
            for row in range(1,maxrow+1):
                combi(col+1,maxcol,maxrow,historique+"("+str(col)+","+str(row)+")")
     
    combi(1,4,2,"");
    combi(1,0,1,"");

    Et les 2 résultats (un tableau 4x2 et un tableau 0x1) :

    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
    (1,1)(2,1)(3,1)(4,1)
    (1,1)(2,1)(3,1)(4,2)
    (1,1)(2,1)(3,2)(4,1)
    (1,1)(2,1)(3,2)(4,2)
    (1,1)(2,2)(3,1)(4,1)
    (1,1)(2,2)(3,1)(4,2)
    (1,1)(2,2)(3,2)(4,1)
    (1,1)(2,2)(3,2)(4,2)
    (1,2)(2,1)(3,1)(4,1)
    (1,2)(2,1)(3,1)(4,2)
    (1,2)(2,1)(3,2)(4,1)
    (1,2)(2,1)(3,2)(4,2)
    (1,2)(2,2)(3,1)(4,1)
    (1,2)(2,2)(3,1)(4,2)
    (1,2)(2,2)(3,2)(4,1)
    (1,2)(2,2)(3,2)(4,2)
    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++

  12. #12
    Membre habitué
    Homme Profil pro
    Directeur des systèmes d'information
    Inscrit en
    mars 2002
    Messages
    129
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France, Lot et Garonne (Aquitaine)

    Informations professionnelles :
    Activité : Directeur des systèmes d'information
    Secteur : Conseil

    Informations forums :
    Inscription : mars 2002
    Messages : 129
    Points : 129
    Points
    129

    Par défaut GRAND MERCI

    Grand merci et bravo. Très élégant. Je n'aurais pas pu trouver... Trop conceptuel pour moi. Tu me sauves la vie

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Combien de combinaison possible pour uniqueidentifier
    Par NicoNGRI dans le forum MS SQL Server
    Réponses: 1
    Dernier message: 26/10/2006, 15h49
  2. Réponses: 16
    Dernier message: 20/10/2006, 16h31
  3. trouver les combinaisons possibles d'un tableau ?
    Par titoumimi dans le forum Algorithmes et structures de données
    Réponses: 12
    Dernier message: 20/09/2006, 20h29
  4. toutes les combinaisons possibles
    Par marocleverness dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 29/05/2006, 00h11
  5. Sortir d'un tableau les combinaisons possibles
    Par juelo dans le forum Algorithmes et structures de données
    Réponses: 33
    Dernier message: 26/03/2006, 17h11

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