Discussion :

[tnarol]

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

[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.

[tnarol]

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.

[loufoque]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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);
}

[tnarol]

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

[loufoque]

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...