Ensemble des partitions d'une liste

Salut,

Je cherche un algo efficace (j'en ai déjà un qui me semble loin d'être optimal) pour obtenir à partir d'une liste d'entiers set<int> la liste des partitions de cette ensemble dont la taille est inférieure à un entier fixé pMax sous forme d'un set<set<int>>.

Par exemple si ma liste initiale est {1, 3, 5, 8} et pMax = 2, je voudrais que l'algo me donne : {{1}, {3}, {5}, {8}, {1,3}, {1,5}, {1,8}, {3,5}, {3,8}, {5,8}}

Merci pour votre aide

C'est un problème d'algorithmique, pas de C++.
A priori une approche naïve en n² ne semble pas être une si mauvaise solution.

Citation:

---

Envoyé par loufoque

C'est un problème d'algorithmique, pas de C++.
A priori une approche naïve en n² ne semble pas être une si mauvaise solution.

---

Disons que comme la STL contient pas mal d'algos il y en a souvent un qui peut aider à faire ces choses là en limitant le codage.

La bibliothèque standard a de quoi générer toutes les permutations, mais pas toutes les partitions.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

std::set<int> set; std::set< std::set<int> > multiset;   foreach(int a, set) { std::set<int> tmp; tmp.insert(a);   foreach(int b, set) { multiset.insert(tmp); tmp.insert(b); } multiset.insert(tmp); }

---

la code précédent ne fait que des paires de valeurs si je ne m'abuse...

Je t'invite à relire le code.
Il y avait un petit cas que j'avais oublié, mais ça n'insère pas que des paires...