Discussion :

[Umbre373]

Bonjour!

Je viens de m'inscrire sur le forum, je pratique la programmation par plaisir, je ne connais que le c++. Je bute sur un problème et je ne sais vraiment pas par quel bout m'y prendre.
Je cherche à générer les permutations d'un ensemble avec répétitions.

Par exemple

AABBBB
ABABBB
ABBABB
ABBBAB
ABBBBA
BAABBB
BABABB
...

Je sais générer toutes les permutations d'un ensemble de n éléments, mais cela donne n! combinaisons possibles, ce qui est énorme en temps de calcul pour des ensembles un peu plus gros. Si je tiens compte des répétitions des éléments du même type j'obtient n!/(n1! * n2! *...*nk!) combinaisons possibles (où n1, n2...nk sont le nombre d'éléments du premier type, du second type... du k-ième type).

Dans mon exemple il existerait 6!=720 combinaisons possibles obtenues avec permutations "simples", et 6!/(2!*4!) = 15 combinaisons possibles obtenues en tenant compte des répétitions du même élément. Là, cela ne fait pas une grande différence, mais sur des ensembles d'une vingtaine d'éléments cela devient vite indispensable, mais je ne sais pas du tout comment m'y prendre...
Si quelqu'un sait comment faire un algo, au moins dans la logique, qui saurait générer tout ça en évitant de calculer tous les doublons, je suis preneur!

[jo_link_noir]

std::next_permutation

[Umbre373]

std::next_permutation

Merci beaucoup! C'est exactement ce que je cherchais. Je pensais devoir le faire moi même, car je ne connais pas bien <algorithm>. Dans mon code ça fonctionne, je vais essayer de comprendre comment elle marche en interne. Encore merci!