Combinaisons à taille variable d'élements

Logiciel & apps Programmation
1

Bonsoir,

Je recherche un algo qui permet de, à partir de l’ensemble E composé de a, b et c (3 élements) de créer la liste suivante :[quote=""]
a
b
c
a, b
a, c
b, c
a, b, c
[/quote]
Bien sûr je recherche un algorithme qui marche quelque soit la taille de l’ensemble.

Que le résultat soit sous forme de chaîne comme la liste de l’exemple donné plus haut, ou sous forme de matrice comme ci-dessous, cela me convient.

1	0	0
0	1	0
0	0	1
1	1	0
1	0	1
0	1	1
1	1	1

J’ai bien remarqué certains schèma, certaines répétitions au sein de la matrice, mais je ne suis pas parvenu à en faire un algorithme.

Après plusieurs heures de recherches Google infructueuses, je n’arrive toujours pas à mettre la main sur un tel algorithme…

Merci d’avance :jap:
Edité le 31/05/2007 à 00:37

2

Ce que tu veux c’est tous les sous ensembles qui composent E au final?

Je sais qu’il y a des algorithmes pour ça, mais je les ai pas en tête.

Néanmoins :

  1. La première série de sous ensemble est celle des ensembles à un éléments
  2. La seconde série de sous-ensemble est celle des ensembles à deux éléments
    …

Partant de ce principe, avec En = {ensemble des sous ensembles à n éléments}, e un élément de En (soit un sous ensemble à n éléments), et E l’ensemble de départ :

Pour i = 2 à card(E):
  Pour chaque élément e de Ei-1:
    F = E \ e;
    Pour chaque élément f de F:
      Ajouter l'élément {e union {f}} à l'ensemble Ei
    Fin
  Fin
  Virer les doublons dans Ei
Fin

A priori ça te renvoie tout :


E = {a, b, c}
i = 2: 
E1 = {{a}, {b}, {c}}
e = {a}:
F = {b, c}
f = b: E2 += {{a}, {b}}
f = c: E2 += {{a}, {c}}
e = {b}:
F = {a, c}
f = a: E2 += {{b}, {a}} // en double
f = c: E2 += {{b}, {c}}
e = {c}:
F = {a, b}
f = a: E2 += {{c}, {a}} // en double
f = b: E2 += {{c}, {b}} // en double
i = 3
E2 = {{a, b}, {a, c}, {b, c}}
e = {a, b}
F = {c}
f = c: E3 += {{a}, {b}, {c}}
e = {a, c}
F = {b}
f = b: E3 += {{a}, {c}, {b}} // en double
e = {b, c}
F = {a}
f = a: E3 += {{b}, {c}, {a}} // en double
E3 = {{a, b, c}}

Et voilà !

Je testerai pas avec un ensemble plus grand.

Donc en gros :

  1. Intersection d’ensemble
  2. Unicité des éléments
  3. Si tu le fais en C, tu vas te faire chier :wink:
  4. Des optimisations sont possibles en fonction du nombre d’éléments dans les sous ensembles (pour éviter la phase de dédoublonnage)
  5. Complexité : oulah, vaut mieux même pas penser que cet algo soit rapide :slight_smile: c’est minimum n^3 si ce n’est e^n.
    Voilà.
3

Sinon, je remarque une chose sur la représentation matricielle binaire proposée par _raynor :

Si on prend un nombre binaire avec un nombre de bits égal au nombre d’éléments, il suffit alors de compter et de récuperer les valeurs de chaque chiffre (ça doit se faire facilement ça en C non ?).

Donc, avec trois éléments :

001
010
011
100
101
110
111

:wink:

4

Même méthode, il suffit de compter entre 1 et 2^(N+1)-1 et de convertir le résultat en binaire, avec N nombre d’éléments.

5

Yep. En C, ça marchera très bien. Pour peu que tu puisses mapper tes éléments à des puissances de 2, et que tu t’amuses à travailler sur des tableaux d’unsigned long/char. (donc en gros, si tu as 3000 éléments (long[94]), t’es parti pour une partie de franche rigolade :))

Surtout qu’il te faudra t’amuser à calculer toutes les décompositions en puissance de 2 possible (eg: 0x2^31 + 1x2^30, etc).

6

En fait, il n’y a rien à calculer du tout, pour avoir toutes les combinaisons, il suffit de boucler entre 1 et 2^n.
si tu as besoin de le stocker dans un tableau (mais c’est vraiment pas indispensable):


(for int i=1;i<=2^n;i++){
  tableau[i]=i;
}

le tableau ne sert pas à grand chose :D, et tu peux calculer 2^n par décalage de bits.

7

sauf que si 2^n est plus grand que la taille d’un int, t’es cuit, et ça va très vite.

8

ah oui c’est vrai, mais il y a les BigInteger en Java qui n’ont pas de limite, et tu peux assez facilement de faire les fonctions “inc” etc. qui calculent du BigInteger, il suffit de reporter le reste.

de toute façons en restant en long, tu peux déjà aller sur un ensemble à 64 éléments, et pour boucler sur des long à 64 bits, tu est de toutes façons limité par le temps processeur: 16. 10^18 éléments avec 10^-9 secondes par boucle au mieux et en gros juste pour l’ordre de grandeur(1GHz)
ça fait 16.10^18* 10^-9= 16.10^9
donc 16 milliards de secondes sachant qu’un siècle fait en gros 3 milliards de secondes, même en oc bien le processeur, c’est pas très utilisable :smiley: (c’est là qu’un proc quantique serait pratique)

Raynor> pour bien comprendre ton problème, il faudrait qu’on sache de quoi tu as besoin exactement: quel algo utilise ça, est-ce que tu doit le stocker dans un tableau, et surtout sur combien d’éléments au maximum tu compte l’utiliser.
:slight_smile:

9

Tiens, c’est pas con ça… Moi qui pensais à décomposer en puissance de 2…

'fin bref, mon algo fonctionne quoi qu’il advienne! :slight_smile:

10

Salut à tous,

Vos conseils m’ont été très utiles, je n’avais pas remarqué qu’il suffisait d’utiliser la representation binaire des entiers de 1 à 2^card(E) (bien que j’avais cherché en ce sens).

Le but était d’obtenir la liste de toutes les gammes (une gamme étant un groupe de produit) de produit possibles avec card(E) produits.

Au final ça doit aller dans un classeur Excel, c’est pour une application de Turf statistique. Vu la limite d’Excel en nombre de ligne (2^16) je limite le nombre de produit à 16 :slight_smile:

Finalement, j’ai codé tout ça en Java, en utilisant POI pour insérer les données dans un classeur Excel.
D’ailleurs, j’ai un mini soucis : avec card(E) <= 14 ça va, le programme génère le tout, mais à partir de 15 j’ai droit à une Exception in thread “main” java.lang.OutOfMemoryError: Java heap space.

Merci bien à tous :jap:

11

il faut paramétrer la taille de la machine virtuelle par -Xms et -Xmx (min et max en Mo) par défaut à 64Mo max je crois
sur serveur, pour optimiser il est préconisé de mettre les 2 paramètres à la même valeur
http://forums.oracle.com/forums/thread.jspa?threadID=308366

voir info avec "java -X"

12

Merci deltree, j’ai même trouvé où règler ça dans Eclipse (paramètres JVM du Run) :slight_smile: