Discussion :

[ramislebob]

Bonjour,
Il faut que je génère la liste de toutes les combinaisons possibles de cardinalité K pour une liste d'élément de N éléments.
Le problème c'est que chacun des éléments de ma liste peut avoir plusieurs états. Il me faut générer toutes les combinaisons possibles de cardinalité K (2< K < N) en prenant en compte les variantes de chacun des éléments, sans mettre dans la combinaison un même élément sous deux états.

Je ne sais pas si je suis très clair, je vais donc vous donner un exemple:
List<Elements> list = (elemA, elemB, elemC)
elemA a 2 états: elemA1, elemA2
elemB a 2 états: elemB1, elemB2
elemC a 2 états: elemC1, elemC2

je dois générer l'ensemble des combinaisons non ordonnées des elements avec les autres peut importe leur état.
Si la cardinalité est 2, je pense que cela donnerait:
(elemA1, elemB1), (elemA1, elemB2), (elemA1, elemC1), (elemA1, elemC2),
(elemA2, elemB1), (elemA2, elemB2), (elemA2, elemC1), (elemA2, elemC2),
(elemB1, elemC1), (elemB1, elemC2),
(elemB2, elemC1), (elemB2, elemC2)

la cardinalité de la liste N est variable. Idem pour la cardinalité K des combinaisons à générer. (il me faudra toutes les combinaisons pour K allant de 2 à N-1)
Mon nombre d'état est fixe (2) pour chacun des éléments de la liste mais tant qu'à faire, je me pose la question d'une solution générique ou chacun des éléments aurait son vecteur d'état de dimension variable.

Quelqu'un a une idée ou déjà fait ce genre de combinatoire?
Mon appli est en C++ mais le langage importe peu.

Merci d'avance!

[wiwaxia]

Bonjour,

À priori, la sélection de (K) éléments pris dans une liste en comportant (N) devrait permettre de réaliser C_N^K = N!/(K!*(N - K)!) combinaisons.

Si de plus chacun de ces éléments présente (E_i) états différents, sans exclusion mutuelle (sont compatibles au sein d'une combinaison donnée tous les états de tous les éléments présents), le nombre de combinaisons possibles devient:

C' = Somme(P(E_i))

expression dans laquelle intervient la somme des produits des nombres d'états des éléments présents dans une combinaison donnée, soit (C_N^K) termes.

Exemple: pour un ensemble de (N = 5) éléments (V, W, X, Y, Z) présentant respectivement (2, 3, 4, 5, 6) états différents, on devrait avoir:
C₅³ = (4*5/2) = 10 combinaisons de 3 termes, et en tenant compte des divers états:
C' = P_VWX + P_VWY + P_VWZ + P_VXY + P_VXZ + P_VYZ + P_WXY + P_WXZ + P_WYZ + P_XYZ avec
# P_VWX = 2 * 3 * 4 = 24
# P_VWY = 2 * 3 * 5 = 30
# P_VWZ = 2 * 3 * 6 = 36
# P_VXY = 2 * 4 * 5 = 40
# P_VXZ = 2 * 4 * 6 = 48
# P_VYZ = 2 * 5 * 6 = 60
# P_WXY = 3 * 4 * 5 = 60
# P_WXZ = 3 * 4 * 6 = 72
# P_WYZ = 3 * 5 * 6 = 90
# P_XYZ = 4 * 5 * 6 = 120 , soit au total: 580 (calculs à vérifier ).

Dans le cas particulier de nombres d'états tous identiques, on obtient C'(N, K, N_E) = (C_N^K)*(N_E)^K , soit:
# C'(N, K, 1) = (C_N^K)*(1^K) = C_N^K dans le cas d'un état unique, et
# C'(3, 2, 2) = (C₃²)*(2²) = 3 * 4 = 12 pour l'exemple que tu as choisi (N = 3, K = 2, N_E = 2).

L'expression générale de (C') est possible, mais vraiment très lourde.

[ramislebob]

re bonjour,
Merci pour ta réponse rapide. En effet je vois maintenant la formule C'(N, K, NE) = C(N,K)*NE^K

Sachant qu'il va me falloir générer l'ensemble des combinaisons de cardinalité K dans N éléments qui ont 2 états pour K variant de 1 à N, j'obtiens
SUM(k=1..N, C(n,k)*2^k)
ce qui donne:
SUM(C(2, k) with 2 states) = 8
SUM(C(3, k) with 2 states) = 26
SUM(C(4, k) with 2 states) = 80
SUM(C(5, k) with 2 states) = 242
SUM(C(6, k) with 2 states) = 728
SUM(C(7, k) with 2 states) = 2186
SUM(C(8, k) with 2 states) = 6560
SUM(C(9, k) with 2 states) = 19682
SUM(C(10, k) with 2 states) = 59048
SUM(C(11, k) with 2 states) = 177146
SUM(C(12, k) with 2 states) = 531440
SUM(C(13, k) with 2 states) = 1594322
SUM(C(14, k) with 2 states) = 4782968
SUM(C(15, k) with 2 states) = 14348906

ça monte vite! Normalement mon N sera inférieur à 10... j'espère...

Du coup je vois mieux comment générer toutes les combinaisons pour un N, K donné:
- d'abord je génère la liste avec le premier état
- puis pour J allant de 1 à N, j'augmente la liste en changeant l'état de l'élément J

sur mon exemple de 2 parmis 3 cela ferait:
iter1: (A1, B1) (A1, C1) (B1, C1)
iter2: (A1, B1) (A1, C1) (B1, C1), (A2, B1) (A2, C1)
iter3: (A1, B1) (A1, C1) (B1, C1), (A2, B1) (A2, C1) , (A1, B2) (B2, C1), (A2, B2)
iter4: (A1, B1) (A1, C1) (B1, C1), (A2, B1) (A2, C1) , (A1, B2) (B2, C1), (A2, B2) , (A1, C2) (B1, C2), (A2, C2) , (B2, C2)

Que pensez vous de cette approche?

Le problème c'est que j'ai une contrainte en plus:
Lorsque je calcule mon ensemble de combinaison K parmis N, List(N, K), je fais un calcul pour chacune des combinaisons.
J'ai donc une MAP avec pour clef une liste, et pour valeur mon résultat.

Pour la génération de l'ensemble de combinaisons K+1 parmis N, je ne suis pas intéressé par celle contenant un sous ensemble de cardinalité K qui a un résultat spécifique dans ma Map.
Serait il possible de générer cet ensemble de combinaisons K+1 parmis N en excluant directement celles qui ne m'intéressent plus?
Cela m'éviterait de les calculer toutes pour ensuite tester pour chacune d'elle tous les sous ensembles de cardinalité K et potentiellement les enlever.

Voyez vous ce que je veux dire?
dans mon exemple en dimension 3, j'avais d'abord calculé l'ensemble des combinaison de cardinalité 1: A1, B1, C1, A2, B2, C2
Supposons que mon calcul me donne le résultat attendu pour A1,
je ne veux donc plus dans ma liste de cardinalité 2 tous les couples contenant A1.
i.e: (B1, C1), (A2, B1) (A2, C1) , (B2, C1), (A2, B2) , (B1, C2), (A2, C2) , (B2, C2)

Une idée de comment générer une telle liste directement? ma méthode simple ne marche plus...

Pour continuer la logique en cardinalité 3, si (A2, B2) et (B2, C2) me donne le résultat attendu, au lieu de la liste complète
(A1, B1, C1) (A2, B1, C1) (A1, B2, C1) (A2, B2, C1) (A1, B1, C1) (A2, B1, C1) (A1, B2, C1) (A2, B2, C1)

je ne suis intéressé que par: (A2, B1, C1) (A2, B1, C1)

[Flodelarab]

Bonjour

Que pensez vous de cette approche?

Elle est foireuse.
Wiwaxia a été très clair : Tu choisis les éléments, puis, tu choisis les états.
Je ne comprends pas que tu listes des AC avant d'avoir lister tous les états des AB.

Serait il possible de générer cet ensemble de combinaisons K+1 parmis N en excluant directement celles qui ne m'intéressent plus?

Oui.

Voyez vous ce que je veux dire?

Un peu. Mais quel est la difficulté ?

Une idée de comment générer une telle liste directement?

Ben déjà, nous ne savons pas où tu es. Dans des boucles imbriquées ? Dans une liste que tu stockes vraiment en mémoire ?

[ramislebob]

Elle est foireuse.
Wiwaxia a été très clair : Tu choisis les éléments, puis, tu choisis les états.
Je ne comprends pas que tu listes des AC avant d'avoir lister tous les états des AB.

Je serais parti d'un algo existant me fournissant la liste des combinaisons utilisant le premier état de chacun des éléments. (Iter1, j'obtiens une liste de C(n,k) éléments)
C'est ensuite que j'imaginais compléter la liste avec une boucle sur chacun des élements pour ajouter les variantes.

Code :

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

1
2
3
4
5
 
for each element
    for each combination of the list
        if the combination contains the element
             add to the list the combination where the state of the element is changed

Ben déjà, nous ne savons pas où tu es. Dans des boucles imbriquées ? Dans une liste que tu stockes vraiment en mémoire ?

Je ne sais pas encore comment je vais partir. Je prends des avis avant car j'aimerais partir sur une direction optimale...
Ça ne m'a pas l'air le cas de la méthode que j'ai décrite, notamment car je ne pourrai pas exclure les combinaisons qui ne m'intéressent pas lors de la construction de la liste...

Je n'ai pas trop d'autres idées, c'est pourquoi je demande...

[wiwaxia]

Je serais parti d'un algo existant me fournissant la liste des combinaisons utilisant le premier état de chacun des éléments. (Iter1, j'obtiens une liste de C(n,k) éléments)
C'est ensuite que j'imaginais compléter la liste avec une boucle sur chacun des élements pour ajouter les variantes ...

Il y a bien une autre piste, encore que je n'en voie pas très bien la finalité ... Celle d'une variable tableau de dimensions approximatives (C_N^K)×((N_E)^K), que l'on peut envisager si les données (N) et (N_E) restent en-deçà de limites raisonnables, conformément aux indications du message (#3): N <~ 10 et N_E = 2 .

Il s'agit apparemment (si j'ai bien compris) de mémoriser:
a) les (C_N^K) combinaisons de (K) termes parmi (N), et
b) la liste correspondante de toutes les combinaisons d'états possibles, soit (N_E)^K.

1°) Les combinaisons (VWX, VWY, VWZ ...) peuvent être représentées d'une manière ordonnée en notation binaire par les nombres ($00111, $01011, $10011 ...), donc par des entiers au plus égaux à (2⁵ - 1 = 31) et tels que la somme de leurs chiffres soit égale à 3 (dans le même système de numération); soit donc en généralisant par des entiers vérifiant: N_max = 2^N - 1 et S_chb = K
2°) Les suites d'états sont représentables d'une manière semblable par les nombres ($001, $010, $011 ... $111) au plus égaux à (2³ - 1 = 7); et pour un nombre d'états quelconque, par un entier écrit en base (N_E) et limité par E_max = (N_E)^K - 1).

Etant donné deux types d'entiers (T_Entier1, T_Entier2) respectivement compatibles avec les limites précédentes (Nmax, Emax), un tableau d'enregistrements comme ci-dessous, dont l'initialisation ne poserait pas de problème, pourrait peut-être convenir:

Code :

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

1
2
3
4
5
TYPE LstE2 = ARRAY[0..Emax] OF T_Entier2;
     Ligne = RECORD  Monome: T_Entier1; ListeE: LstE2  END;
     Tab_L = ARRAY[1..Cnk] OF Ligne;
 
VAR Tableau: Tab_L;