1. #1
    Membre du Club
    Homme Profil pro
    Ingénieur bioinformaticien
    Inscrit en
    avril 2010
    Messages
    139
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 29
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur bioinformaticien
    Secteur : Santé

    Informations forums :
    Inscription : avril 2010
    Messages : 139
    Points : 49
    Points
    49

    Par défaut Lister toutes les combinaisons de taille n à partir d'une liste d'élements de taille N

    Bonjour.

    Je m'arrache les cheveux depuis quelques jours sur un problème d'algorithmique.
    Sur le net, j'ai déjà trouvé des solutions s'en approchant mais je ne parviens pas à obtenir ce que je souhaite pour autant.

    Voici mon problème initial :

    J'ai une liste d'éléments de taille N, chaque élément étant différent des autres.
    Je souhaite lister toutes les combinaisons possibles de longueur n (combinaisons, et non permutations, donc l'ordre n'est pas important ; avec 0 < n <= N) , en sachant qu'il peut y avoir répétition de chaque élément. L'ordre n'est pas important car chaque élément est pondéré, et au final je souhaite faire la somme de chaque pondération. Donc si j'ai AB et BA, avec A=1 et B=2, ma somme sera la même (3).

    Un exemple sera beaucoup parlant (je l'espère ... ) :

    Liste d'éléments : A - B - C - D - E
    Longueur des combinaisons souhaitée : 2
    Je veux obtenir :

    AA
    AB
    AC
    AD
    AE
    BC
    BD
    BE
    CC
    CD
    CE
    DD
    DE
    EE
    Mais pour des longueurs supérieures, cela devient plus compliqué :

    Longueur : 3

    AAA
    AAB
    AAC
    AAD
    AAE
    ABB
    ABC
    ABD
    ABE
    ACC
    ACD
    ACE
    ADD
    ADE
    AEE
    BBB
    BBC
    BBD
    BBE
    ...
    En gros, c'est comme si on avait une machine à sous avec n rouleaux (slots), et que je voulais toutes les combinaisons possibles (chaque rouleau étant constitué de ma liste initiale), et qu'on retirait ensuite les doublons (car pour une longueur de 3 par exemple, ABC = ABC = BCA = BAC = ...).

    Je pense qu'on peut s'en sortir avec la récursivité mais je débute dans ce domaine, et j'ai un peu de mal à créer mon algo.

    Difficulté supplémentaire, je dois ensuite coder cet algo en VBA Excel (mais je code pas mal en VBA Excel donc ce n'est pas ce qui m'inquiète le plus).

    Désolé si ce problème a déjà été traité dans un autre post, mais j'ai bien parcouru le forum et d'autres sites/forums et je ne trouve rien qui puisse m'aider.

    Merci pour votre aide !

  2. #2
    Membre expérimenté Avatar de vttman
    Homme Profil pro
    Développeur COBOL et le WE (CSS, PHP, JS et MYSQL)
    Inscrit en
    décembre 2002
    Messages
    714
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur COBOL et le WE (CSS, PHP, JS et MYSQL)
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2002
    Messages : 714
    Points : 1 344
    Points
    1 344

    Par défaut

    Je crois que cette discussion peut aider https://www.developpez.net/forums/d1...mbinaison-k-n/
    Je suis sympa comme tout Mosellan mais ...
    ... (m')aider ou (me) mettre sur la voie c'est une chose
    ... tout (me) faire de A à Z, c'est pas ma conception du rôle d'un forum X ou Y
    Si vous n'êtes pas satisfait de mes réponses, n'hésitez pas à me le faire savoir Merci !

  3. #3
    Responsable Qt


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

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

    Informations forums :
    Inscription : août 2008
    Messages : 22 501
    Points : 123 992
    Points
    123 992

    Par défaut



    Une idée, pour la récursivité, est la suivante. Chaque élément de ta liste de taille N peut être pris ou non. Une liste de longueur n est constituée d'une liste de longueur n-1 et d'un nouvel élément. Ta fonction traite le premier élément de la liste de taille N et retourne toutes les possibilités dans deux cas : soit le premier élément est inclus (le premier élément est toujours retourné, puis appel récursif de la fonction avec une longueur n-1 pour générer la suite des combinaisons), soit il ne l'est pas (appel récursif de la fonction avec une longueur n et une liste amputée du premier élément).

    Tente d'abord un peu sur papier, puis passe au code . Normalement, tu ne devrais pas générer de doublons de la sorte, puisque l'on diminue soit le nombre d'items à générer, soit la liste dont ils sont tirés.
    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 !

  4. #4
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 536
    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 536
    Points : 3 193
    Points
    3 193

    Par défaut

    Il y a cette discussion aussi qui aborde un besoin très similaire : https://www.developpez.net/forums/d1...12-caracteres/

    Toi, tu veux en plus retirer les doublons du type ABC = ACB = BAC ...

    Pour cela, tu peux mettre comme contrainte : si j'ai un alphabet de 26 lettres, et des mots de 3 lettres, si la première lettre est L par exemple, je vais prendre comme 2ème lettre uniquement le sous alphabet LMNOP...XYZ, et idem, si les 2 premièers lettres sont LN par exemple, la 3ème lettre sera à choisir parmi le sous-alphabet NOPQ...XYZ.

    Par rapport à ce qui est décrit dans le lien en question, c'est un aménagement relativement simple.

    Après, il faut l'adapter en VBA.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  5. #5
    Membre expert
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 488
    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 488
    Points : 3 944
    Points
    3 944

    Par défaut

    salut

    pour éviter les "doublons" il suffit de trier les éléments que tu cherche et de vérifier que celle-ci n'existe pas déjà dans la liste
    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. Réponses: 0
    Dernier message: 04/02/2013, 14h03
  2. Code pour lister toutes les combinaisons
    Par tontonced dans le forum Macros et VBA Excel
    Réponses: 17
    Dernier message: 28/11/2011, 16h03
  3. Réponses: 12
    Dernier message: 20/04/2011, 23h14
  4. Lister toutes les combinaisons d'éléments
    Par Loceka dans le forum Prolog
    Réponses: 5
    Dernier message: 15/04/2007, 01h11
  5. Lister toutes les combinaisons...
    Par monstroplante dans le forum Général Algorithmique
    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