Bonjour à tous,
Mon problème traite de la détermination de toutes les combinaisons p parmi n éléments, avec des contraintes. Je suis conscient qu'il y a déjà eu de nombreuses réponses à ce genre de problèmes, mais je n'ai pas trouvé de discussion qui m'éclaire réellement. Par ailleurs, on trouve généralement des bouts de code dans des langages précis, je serai plutôt intéressé par une explication en français d'un algorithme (d'où la place de la discussion).
Voici le problème :
On dispose d'un vecteur de n éléments -qui sont des couples d'indices- de la forme suivante :
V = [{i1,j1},{i2,j2},...,{ik,jk}]
Ce que je veux faire, c'est extraire toutes les combinaisons de ces éléments (de dimension 1 à la dimension maximale autorisée par les contraintes) telles que les indices i soient différents.
Je m'explique sur un exemple de taille réduite :
Soit V = [{1,1},{1,3},{3,4}]
Les combinaisons de dimension 1 sont les éléments seuls :
{1,1}
{1,3}
{3,4}
Les combinaisons de dimension 2 telles que les indices "i" soient différents sont :
[{1,1},{3,4}]
[{1,3},{3,4}]
2 est la dimension maximale autorisée car en dimension 3, on aurait deux éléments avec l'indice "i" identique.
J'espère que l'énoncé est compréhensible et le problème bien posé. Une solution barbare serait de calculer toutes les combinaisons de p parmi n (avec un algorithme récursif par exemple) en faisant varier p de 1 à n, puis d'enlever les éléments ne répondant pas au problème. Sur l'exemple cela donne :
{1,1} => ok
{1,3} => ok
{3,4} => ok
{1,1}{1,3} => A retirer
{1,1}{3,4} => ok
{1,3}{3,4} => ok
{1,1}{1,3}{3,4} => A retirer
Je me demandais si quelqu'un aurait une meilleure idée...
Merci par avance.
Partager