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 :

[combinatoire] combinaisons de toutes longueur


Sujet :

Algorithmes et structures de données

  1. #1
    Futur Membre du Club
    Profil pro
    Inscrit en
    Février 2003
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Février 2003
    Messages : 6
    Points : 7
    Points
    7
    Par défaut [RESOLU][combinatoire] combinaisons de toutes longueur
    salut à tous,

    quelqu'un aurait-il une idée pour un algorithme permettant de trouver toutes les combinaisons simples (sans ordre, sans répétition) de N éléments pris par groupes de 1 à N.

    Un petit exemple : soient 3 éléments A,B,C

    l'algorithme devrait retourner :

    A
    B
    C
    AB
    AC
    BC
    ABC

    Mon but n'est donc pas de connaître le nombre de combinaisons, mais bien d'obtenir toutes ces combinaisons.

  2. #2
    Membre habitué

    Profil pro
    Inscrit en
    Octobre 2002
    Messages
    66
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2002
    Messages : 66
    Points : 129
    Points
    129
    Par défaut
    1- As-tu lu l'annonce faite en début de cette section Algo concernant les anagrammes et autres applications de la récursivité ?

    2- Le principe est d'explorer en profondeur les combinaisons en utilisant la récursivité comme solution élégante.
    Si tu as Delphi, j'ai donné le code complet de ce que tu recherches à cet endroit (mais tu pourras l'adapter facilement à d'autres langages à condition de connaître les principes des fonctions récursives) :
    http://www.developpez.net/forums/vie...t=combinaisons

    A+
    Consultez :
    - La F.A.Q Delphi + Les Cours Delphi
    - La sélection des Freewares Delphi

  3. #3
    Membre averti
    Avatar de JHelp
    Inscrit en
    Octobre 2002
    Messages
    185
    Détails du profil
    Informations forums :
    Inscription : Octobre 2002
    Messages : 185
    Points : 444
    Points
    444
    Par défaut
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
     
    afficherCombinason(chaine : Chaine,liste : liste des elments) 
       Si liste est vide Alors
           afficher chaine
       Sinon
          tete <-- tete de la liste
          afficher chaine ^ tete
          queue <-- queue de la liste
          Si queue n'est pas vide Alors
              afficherCombinaison&#40;chaine,queue&#41;  
              afficherCombinaison&#40;chaine ^ tete,queue&#41;
           Fin-Si
       Fin-Si
    Fin-afficherCombinaison
    Ce qui donne pour ton exemple :
    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
     
    afficherCombinaison("",{A,B,C})
    1) {A,B,C} nest pas vide
    2) tete = A
    3) on affiche A
    4) queue = {B,C}
    5) queue n'est pas vide
    6) appel de afficherCombinaison("",{B,C})
        6)1) {B,C} n'est pas vide
        6)2) tete=B
        6)3) on affiche B
        6)4) queue={C}
        6)5) queue n'est pas vide
        6)6) appel de afficherCombinaison("",{C})
               6)6)1) {C} n'est pas vide
               6)6)2) tete = C
               6)6)3) on affiche C
               6)6)4) queue={}
               6)6)5) queue est vide
               6)6)7) FIN
         6)7) appel de afficherCombinaison("B",{C})
               6)6)1) {C} n'est pas vide
               6)6)2) tete = C
               6)6)3) on affiche BC
               6)6)4) queue={}
               6)6)5) queue est vide
               6)6)7) FIN
          6)9) FIN
    7) appel de afficherCombinaison("A",{B,C})
    .....
    Ce qui donne :
    A
    B
    C
    BC
    AB
    AC
    ABC
    JHelp
    Pour avoir une réponse efficace :
    1) Soyez précis dans vos questions
    2) Choisssez bien votre forum
    3) Consultez la FAQ et la doc avant

  4. #4
    Futur Membre du Club
    Profil pro
    Inscrit en
    Février 2003
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Février 2003
    Messages : 6
    Points : 7
    Points
    7
    Par défaut
    Ok merci pour vos réponses (et désolé si la solution avait déjà été exposée sur le forum), je m'en vais de ce pas marquer ma question [RESOLU]

  5. #5
    Membre à l'essai
    Profil pro
    Inscrit en
    Novembre 2002
    Messages
    15
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Novembre 2002
    Messages : 15
    Points : 16
    Points
    16
    Par défaut implémentation en java
    private static void affiche(ArrayList str,ArrayList reste)
    {

    if (reste.isEmpty())
    {
    System.out.println(str.toString());
    }
    else
    {
    String tete = (String)reste.get(0);
    reste.remove(0);
    System.out.println(str.toString()+tete);

    if (!reste.isEmpty())
    {
    // chaine, queue
    affiche(str,reste);
    // chaine & tete,queue
    str.add(tete);
    affiche(str,reste);

    }
    }

    J'appelle cette fonction avec reste qui [a,b,c] et str qui vaut [""] et voici le résultat :

    []a
    []b
    []c
    [b]
    [b, a]
    []

    Il me manque des résultats !!!

    Quelqu'un a une idée sur ce qui coince ?

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

Discussions similaires

  1. Réponses: 16
    Dernier message: 20/10/2006, 17h31
  2. Avoir toutes les combinaison
    Par guigui76esi dans le forum Algorithmes et structures de données
    Réponses: 7
    Dernier message: 18/10/2006, 18h53
  3. toutes les combinaisons possibles
    Par marocleverness dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 29/05/2006, 01h11
  4. retouver toute les combinaison
    Par sami_c dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 22/03/2006, 21h09
  5. Lister toutes les combinaisons...
    Par monstroplante dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 04/11/2005, 22h10

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