Discussion :

[weezer]

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.

[SpiceGuid]

Ma notation:

• les vecteurs: [i;..;j]
• les ensembles: {i,...,j}
• les paires: (i,j)

Il faut partitionner ton vecteur suivant l'élément i des couples, c'est-à-dire qu'à partir de ceci:

V0 = [(1,1);(1,3);(2,3);(3,4);(3,5)]

Il faut obtenir cela:

V1 = [[(1,1);(1,3)];[(2,3)];[(3,4);(3,5)]]

Ensuite il faut adapter l'algo de combinaisons d'un vecteur pour qu'il utilise tous les éléments des sous-vecteurs.

Code OCaml :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
let rec flatten_map_append f l1 l2 =
  match l1 with
  | [] -> l2
  | h::t -> flatten_map_append f t (f h @ l2)
      
let rec combinate n l =
  if n = 0 then [[]] else
  match l with
  | [] -> []
  | vect::t ->
      let head = combinate (n-1) t in
      let tail = combinate n t in
      flatten_map_append
      (fun h -> List.map (fun x -> h::x) head @ tail)
      vect []

Code OCaml :

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

1
2
3
4
5
6
# let v1 = [[(1,1);(1,3)];[(2,3)];[(3,4);(3,5)]];;
# combinate 2 v1;; (* combinaisons de 2 éléments parmi v1 *)
- : (int * int) list list =
[[(1, 3); (2, 3)]; [(1, 3); (3, 5)]; [(1, 3); (3, 4)]; [(2, 3); (3, 5)];
 [(2, 3); (3, 4)]; [(1, 1); (2, 3)]; [(1, 1); (3, 5)]; [(1, 1); (3, 4)];
 [(2, 3); (3, 5)]; [(2, 3); (3, 4)]]

Remarque: il y a des répétitions, par exemple [(2, 3); (3, 5)] et [(2, 3); (3, 4)] sont présents deux fois, mais c'est tout de même un bon début.

[Trap D]

je serai plutôt intéressé par une explication en français d'un algorithme (d'où la place de la discussion).

OCaml est un langage d'origine française, mais tout de même