Bonjour,

Je cherche a lister toutes les possibilités de combinaisons d'un certain nombre d'élément, sachant que:

• Chaque élément est unique
• L'ordre n'a pas d'importance
• Chaque element a un poids

En gros, il s'agit d'une variante de l'algorithme du sac a dos, mais ou le nombre d'élément est beaucoup plus grand que la taille de celui-ci, et ou on peut s'arreter avant le remplissage. De plus, il y a bien un "poids" pour chaque element, mais pas de "valeur" permettant de faire un algorithme glouton. (De toute façon, je voudrais toutes les possibilités)

Avec un exemple, ça sera plus clair:

my_tab = [1,2,3,4]

j'essaye d'avoir un tableau de sortie comme ceci:

[
 [1],[2],[3],[4],
 [1,2],[1,3],[1,4],[2,3],[2,4],[3,4],
 [1,2,3], [1,2,4],[1,3,4],[2,3,4],
 [1,2,3,4]
]

Sachant que ici, pour  simplifier, j'ai mis le poids de chaque element a 1, et la taille du sac à 4.

Merci

Tu pars d'un tableau de n éléments. Tu auras donc des possibilités qui auront de 1 à n éléments dedans.

Personnellement, je ferais un truc de ce genre :

A partir d'un tableau de n éléments, tu peux sortir n possibilités qui seront les n élements, ici, [1],[2],[3],[4].

Ensuite, tu prends ta liste d'ensemble à 1 élément, et pour chacun d'entre eux, tu leur ajoutes un élément parmi tous ceux qui ont un index supérieur au leur dans le tableau initial. Ça te donnera tes couples [1,2],[1,3],[1,4],[2,3],[2,4],[3,4]

En gros, à partir de [1], tu lui rajoutes 2, puis 3 puis 4.

Pour [2], tu lui rajoutes 3 puis 4, etc...

Ensuite pour tous tes couples  [1,2],[1,3],[1,4],[2,3],[2,4],[3,4], tu prends chacun d'entre eux, et tu leur rajoutes un élément parmi tous ceux qui ont un index supérieur à l'élément avec le plus grand index dans le tableau initial.

Donc, exemple pour [1,2] :

2 est l’élément avec le plus grand index, donc tu rajoutes 3 puis 4, ca te donnera [1,2,3], [1,2,4].

Puis idem avec tous les autres couples. tu noteras vite que les couples qui ont un 4 ne donneront rien de plus, car 4 est déjà le dernier élément du tableau initial.

Ensuite pour tous tes triplets, tu fais pareil, tu leur rajoute pour chaque tous les éléments qui ont un index supérieur, blablabla...

Ce qui donne pour [1,2,3], tu rajoutes 4.

Pour les autres, vu qu'il y a déjà un 4, ça ne donne rien.

C'est assez simpliste dans le fond. En développant ça, il y a sans doute moyen d'ajouter des micro optimisations (genre si tu pars d'un ensemble qui contient déjà le dernier élément, tu ne fais rien.

J'avais bien un autre algo bourrin en tête, mais je pense que la complexité serait encore pire.

Pour chaque valeur de la liste, tu as la possibilité de le prendre ou pas.

Option récursive : ta liste de combinaisons

[ [1],[2],[3],[4], [1,2],[1,3],[1,4],[2,3],[2,4],[3,4], [1,2,3], [1,2,4],[1,3,4],[2,3,4], [1,2,3,4] ]

peut s'interpréter comme ceci : si tu peux calculer les combinaisons de [2, 3, 4], alors les combinaisons de [1, 2, 3, 4] sont l'union :
- des combinaisons de [2, 3, 4] (je ne prends pas 1)
- et des combinaisons de [2, 3, 4] auxquelles on a ajouté 1 (je prends 1).

Exemple des différents appels récursifs :
- combinaisons [1, 2, 3, 4] =
    (combinaisons [2, 3, 4]) union (combinaisons [2, 3, 4] avec 1 en tête)
- combinaisons [2, 3, 4] =
    (combinaisons [3, 4]) union (combinaisons [3, 4] avec 2 en tête)
- combinaisons [3, 4] =
    (combinaisons [4]) union (combinaisons [4] avec 3 en tête)
- combinaisons [4] =
    (combinaisons []) union (combinaisons [] avec 4 en tête)
- combinaisons [] = [[]] (ie une combinaison à 0 élement)

et c'est dans la poche.

-
Edité par cvanaret 19 décembre 2018 à 11:24:54

cvanaret a écrit:

Pour chaque valeur de la liste, tu as la possibilité de le prendre ou pas.

Option récursive : ta liste de combinaisons

[ [1],[2],[3],[4], [1,2],[1,3],[1,4],[2,3],[2,4],[3,4], [1,2,3], [1,2,4],[1,3,4],[2,3,4], [1,2,3,4] ]

peut s'interpréter comme ceci : si tu peux calculer les combinaisons de [2, 3, 4], alors les combinaisons de [1, 2, 3, 4] sont l'union :
- des combinaisons de [2, 3, 4] (je ne prends pas 1)
- et des combinaisons de [2, 3, 4] auxquelles on a ajouté 1 (je prends 1).

Je t'avoue que je ne comprends pas ton algo. Le cas [1,2,4] apparaîtrait à quel moment dans ton algo ?

Sinon par récursion, tu peux effectivement partir du cas le plus complexe [1,2,3,4] et retrouver toutes les combinaisons qui contiennent un élément de moins, donc [1,2,3], [1,2,4],[1,3,4],[2,3,4].

Pour chacun de ce triplet, tu fais pareil, et ca de manière récursive jusqu'à n'avoir que des ensembles à 1 élément.

Le soucis, c'est que tu auras plein de doublons, il faudra ensuite faire un petit tri.

Le cas [1, 2, 4] apparaîtra lorsque tu génères d'abord [4], puis on ne prend pas 3, puis on prend 2, puis on prend 1.
L'approche récursive ne travaille pas des cas complexes vers les cas simples, mais des cas simples vers les cas complexes.

Si je dépile les appels récursifs et que j'affiche ca dans le bon ordre :
- on génère d'abord des combinaisons de [] : on obtient [[]]
- on considère 4 : on le prend ou non. On obtient donc ([[4]] union [[]]) = [[4], []]
- on considère 3 : on le prend ou non. On obtient donc ([[3, 4], [3]] union [[4], []]) = [[3, 4], [3], [4], []]
- on considère 2 : on le prend ou non. On obtient donc ([[2, 3, 4], [2, 3], [2, 4], [2]] union [[3, 4], [3], [4], []]) = [[2, 3, 4], [2, 3], [2, 4], [2], [3, 4], [3], [4], []]
- on considère 1 : on le prend ou non. On obtient donc ([[1, 2, 3, 4], [1, 2, 3], [1, 2, 4], [1, 2], [1, 3, 4], [1, 3], [1, 4], [1]] union [[2, 3, 4], [2, 3], [2, 4], [2], [3, 4], [3], [4], []]) = toutes les combinaisons

A aucun moment il n'y a de doublons.


Edit : pour le plaisir, un petit code en Caml :

let rec combinaisons liste = match liste with
  | [] -> [[]]
  | t :: q ->
      let combinaisons_q = combinaisons q in
      List.map (fun combinaison -> t :: combinaison) combinaisons_q @ combinaisons_q
;;

# combinaisons [1; 2; 3; 4];;
- : int list list =
[[1; 2; 3; 4]; [1; 2; 3]; [1; 2; 4]; [1; 2]; [1; 3; 4]; [1; 3]; [1; 4]; 
 [1]; [2; 3; 4]; [2; 3]; [2; 4]; [2]; [3; 4]; [3]; [4]; []]

-
Edité par cvanaret 19 décembre 2018 à 15:10:49

Effectivement, c'est clean.

Dans ta liste, il y a l'ensemble vide qui apparaît en plus par rapport  à la demande initiale... Je crois que tous les programmes 'simples' vont mettre cet ensemble vide.

On a donc 2x2x2x2=16 ensembles dans ce cas. Et si on ne veut pas de cet ensemble vide, il faut l'enlever 'après coup'.

Exact, c'est la combinaison à 0 élément.
Ici, elle est nécessaire pour le bon fonctionnement de la fonction récursive, mais effectivement on peut l'enlever après coup.

Salut,

J'ai fais, avec l'aide d'autres devs, cet algo:

var final = [] ;
for(var el in list_of_elements){
	for(var final_el in final){
		final.append(final_el+[el]) ;
	}
	final.append([el]) ;
}

J'ai fais quelques test, et il semble plutot bien fonctionner.

Malheureusement, le "poids" des  elements n'est pas pris en compte de façon direct par l'algorithme, ce qui fait que de nombreux cas futiles sont générés. J'ai donc rajouté une condition au "append" pour verifier qu'on ne dépasse pas. Mais c'est assez couteux.

J'ai tout de même gardé celui ci, car il est assez simple.

Je dois maintenant en faire une sorte de "v2", qui prend en compte toujours ce poids (il y en a même deux, qui ne peuvent être dépassés) mais qui par contre est dépendent de l'ordre (enfaite c'est le second poids qui dépend de l'ordre ...) et ou un élément peut se retrouver plusieurs fois.

J'étais partis dans des bloucles for en grand nombre, mais c'est vraiment pas optimal ... avez vous une idée ?

Merci

Ce n'est pas totalement clair ... mais je pense être sur la bonne piste.

Si on reste sur 4 éléments, tu as en fait 4 triplets (identité, poids, taille).

Tu veux toutes les combinaisons de ces 4 individus, avec comme contrainte Somme(Poids) <= un certain seuil.

Ca tu dois pouvoir l'implémenter assez facilement sur la base de ce que tu as. A ce niveau, tu as donc des groupes d'individus ordonnés (tu peux avoir [1,2,4], mais pas [1,4,2] ni [4,1,2] ... )

Mais quand tu as un groupe d'individus qui vérifie la contrainte sur le poids,  tu peux assez facilement appeler un autre sous-programme, qui va recenser toutes les permutations de ces individus (à partir de n individus, il y a n! permutations) , et qui va vérifier si la 2ème contrainte sur la taille est respectéé.

[1,2,4] ok sur la contrainte poids, donc on analyse [1,2,4], [1,4,2], [2,1,4],[2,4,1], [4,1,2] et [4,2,1] sur la contrainte taille.

PS : le lien dans ta signature n'est plus valide.

-
Edité par tbc92 20 décembre 2018 à 9:36:45

Salut,

tout d'abord, il faut savoir que je cherche a faire cela pour le cout le plus dérisoire possible, donc que tout calculer pour ensuite supprimer est une très mauvaise option pour moi.

Ensuite, j'aime bien ta solution, mais le soucis, c'est qu'elle ne prend pas en compte le fait qu'une élément peut apparaitre plusieurs fois.

Merci