Discussion :

[Nemerle]

Allez, j'ai un tableau que je représente ici comme une partie X de N^n. J'aimerais trouver la plus petite "partition" P1,P2...,Pm de X, au sens où

1. Chaque Pi est produit d'ensembles de N: P=A1xA2x...xAn (les Aj variant pour chaque Pi)
2. X est réunion disjointe des Pi.

What is le meilleur algo?

[pseudocode]

1. Chaque Pi est produit d'ensembles de N: P=A1xA2x...xAn (les Aj variant pour chaque Pi)

Je n'ai pas bien compris le probleme. C'est quoi les Ai, des elements de N ? Et la notation A1 x A2, c'est la multiplication ?

Hum... ca ne doit pas etre ca, car dans ce cas je ne vois pas de "contrainte" pour le partitionement.

[Nemerle]

Je n'ai pas bien compris le probleme. C'est quoi les Ai, des elements de N ? Et la notation A1 x A2, c'est la multiplication ?

Les Ai sont des sous-ensembles de N. A1xA2 est le produit cartésien.

Plus simplement, par exemple P1 = {1,2,4}x{2,3}x{5,7}. L'élément (2,3,7) par exemple appartient à P1.

[pseudocode]

Je me disais aussi que c'était trop facile.

Hum... ça m'a tout l'air d'un problème de MCSC (Minimum Consistent Subset Cover).

Bon, alors on a toujours l'approche Greedy qui est simple mais qui ne donne pas forcement la solution optimale, a moins de faire une exploration exhaustive (et d'acheter un Cray).

Sinon, il y a les algorithmes CAG (Clustered AGgregation) qui semblent être des bon candidats pour les problèmes de MCSC. Il faut voir ce qu'en pense mon ami google, avec les mots clés MCSC et CAG.

[Nemerle]

Je me disais aussi que c'était trop facile.

Hum... ça m'a tout l'air d'un problème de MCSC (Minimum Consistent Subset Cover).

.

Oui, c''est bien cela pseudocode. Le problème est que ma contrainte n'est pas consistante, ni même "pivot"-consistante. MCSC et CAG ne s'appliquent donc pas.

Ici, il faut donc essayer de faire "au mieux".... la taille du tableau n'est pas trop grande, maximum 10 colonnes pour 200-300 lignes.

L'objectif est en fait de présenter dans une IHM des paramètres administrateurs par "paquets". Exemple:

Filiale Département Profil_User droits

L'objectif est d'obtenir par exemple

{f1,f3,f5}-{d2,d4}-{p3,p5,p6}-{droit1,droit3,droit5} indiquant que toutes les combinaisons possibles par "produit" sont ok (par exemple (f3,d4,p5,droit3)).


Donc ce que je cherche ici, c'est de comparer des idées afin de "maîtriser" autant que faire se peut les temps de calcul...

Je donnerais ma vision demain ou après-demain.

[Nemerle]

Bon, on a X dans N^n, notons (x1,...,xn) les composantes de tout x dans X.

1. Disons que pour deux éléments distincts x,y de X, x~y si toutes les composantes de x et y sont égales SAUF une.

2. On considère le graphe (non orienté) de sommets les x de X; un arrête relie x et y ssi x~y.

3. On fait alors une recherche heuristique en regardant les cycles du graphe.....

Qu'en pensez-vous?


Un exemple:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
x	x1	x2	x3	x4
1	1	4	7	9
2	1	4	8	9
3	1	5	7	9
4	1	5	8	9
5	1	6	7	9
6	1	6	8	9
7	2	4	7	9
8	2	4	8	9
9	2	5	7	9
10	2	5	8	9
11	2	6	7	9
12	2	6	8	9
13	3	4	7	9
14	3	4	8	9
15	3	5	7	9
16	3	5	8	9
17	3	6	7	9
18	3	6	8	9

Le cycle 1->13->17->18->16->14->8->2->6->4->10->12->11->5->3->15->9->7->1
montre que X={1,2,3}x{4,5,6}x{7,8}x{9}.