Je fais appel à votre savoir pour un problème sur lequel je n'arrive pas à aboutir.
Voici la problématique : Comment trouver le nombre de permutations uniques de sous-ensembles C de cardinalité P d’un multiensemble S de cardinalité N ?
J'ai trouvé un post sur un autre site qui en parle : https://math.stackexchange.com/questions/114654/permutations-of-subsets-of-a-multiset. C'est globalement ce que je veux, mais j'aimerais savoir s'il y avait un moyen de simplifier encore plus la formule trouvée.
Voici un exemple qui permettra sûrement d'éclaircir mes propos :
- Imaginons que je possède 3 éléments
- Je souhaite trouver combien il existe de façon de prendre 2 éléments parmi ces éléments
- Cependant, je ne souhaite pas compter les doublons : comme on a deux
et
par exemple,
est équivalent à
- Sachant cela, les solutions possibles sont donc
. On en compte 3
D'après le lien donné plus haut, une méthode pour compter cela est la suivante :
- On construit une liste
qui, à chaque élément unique des éléments de base, associe le nombre de fois qu'il apparaît. On aurait donc ici
- Ensuite, on détermine les partitions de taille 2 dont la somme des éléments donnent 2 :
- Finalement, en appliquant la formule donnée, le nombre total de solutions serait
. On retrouve bien ce qu'on avait déterminé à la main
Est-il possible de simplifier le processus ? L'idée est par la suite d'écrire un programme pour le faire. Je l'ai déjà fait, mais il est malheureusement lent pour des grosses entrées. C'est pour cela que je souhaite réduire au maximum les calculs à effectuer.
J'espère avoir été clair, n'hésitez pas à poser des questions.