Discussion :

[phoenix420]

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 !

[vttman]

Je crois que cette discussion peut aider https://www.developpez.net/forums/d1...mbinaison-k-n/

[dourouc05]

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.

[tbc92]

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.

[anapurna]

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