Extraire des sous ensembles dans un tableau

Version imprimable

13/03/2017, 17h50
lepatantpato

Extraire des sous ensembles dans un tableau

Bonjour tout le monde

Dans un tableau j'ai les combinaisons suivantes :

/ 1 2 3 4

A 1 1 1 0
B 1 1 0 1
C 1 0 1 1
D 0 1 1 0
E 1 1 0 0
F 1 1 1 0

Je désire supprimer les doublons de sous-ensembles et ne garder que les valeurs
minimales communes.
Par exemple :
E utilise les colonnes 1 et 2
et 1 et 2 sont également compris dans A et B
donc je voudrais éliminer A et B.
D utilise les colonnes 2 et 3
F utilise également 2 et 3, donc je voudrais éliminer F.
Au final, je garde C D et E.

/ 1 2 3 4

C 1 0 1 1
D 0 1 1 0
E 1 1 0 0

Quelqu'un aurait une idée d'algo ?
j'ai bien développé une solution, mais elle prend trop de temps quand le tableau dépasse une dizaine colonnes et plein de lignes....
Ce que j'ai fait :
Lecture séquentielle de chaque ligne et comparaison avec toutes les autres; cela fonctionne mais est vite rédhibitoire en temps de calcul...:
Merci.
13/03/2017, 19h30
tbc92

Pour chaque ligne, je calculerais un compteur :
A 1 1 1 0 --> 3
B 1 1 0 1 --> 3
C 1 0 1 1 --> 3
D 0 1 1 0 --> 2
E 1 1 0 0 --> 2
F 1 1 1 0 --> 3

Je trierais sur cette colonne :
D 0 1 1 0 --> 2
E 1 1 0 0 --> 2
A 1 1 1 0 --> 3
B 1 1 0 1 --> 3
C 1 0 1 1 --> 3
F 1 1 1 0 --> 3

Et j'ai l'impression qu'on a fait 95% du boulot :

Je prends D, donc je vire A F
Je prends E, doc je vire B
Et il ne m reste que C, que je prends forcément.
14/03/2017, 13h37
lepatantpato

suite

Bonjour
Oui, c'est vrai,: mais le problème est :
comment définir que si je garde D, je vire A et F ?
pour cela, il faut comparer D avec E, A , B C et F.
L'algo que j'ai construit pour l'instant fait cette comparaison, c'est pour cela qu'il est très lent dès
qu'on a beaucoup de lignes et/ou de colonnes...
Voici ce que j'ai fait.
Je vais comparer chaque ligne avec toutes les suivantes, et j'élimine les doublons.

tri préalable sur la colonne compteur
puis je lis chaque ligne avec toutes les suivantes
J"incrémente une colonne Memorise si je trouve une correspondance.
Exemple :

je démarre en D,
je trouve en D colonne 2 >0 donc en Memorise, j'ajoute 1
puis je lis toutes les lignes de E a F : si colonne 2 >0 donc Memorise=+1

1 2 3 4 Memorise
D 0 1 1 0 => 1
E 1 1 0 0 => 1
A 1 1 1 0 => 1
B 1 1 0 1 => 1
C 1 0 1 1 => 0
F 1 1 1 0 => 1

je suis toujours en ligne D
je trouve en D colonne 3 >0 donc en Memorise, j'ajoute 1
puis je lis toutes les lignes de E a F : si colonne 3 >0 donc Memorise=+1

1 2 3 4 Memorise
D 0 1 1 0 => 2
E 1 1 0 0 => 1
A 1 1 1 0 => 2
B 1 1 0 1 => 1
C 1 0 1 1 => 1
F 1 1 1 0 => 2

J'ai fini la ligne D. Je vais supprimer toutes les lignes dont Memorise contient 2 (sauf D, le point de départ)

1 2 3 4 Memorise
D 0 1 1 0 => 2
E 1 1 0 0 => 1
B 1 1 0 1 => 1
C 1 0 1 1 => 1

Je passe à ligne suivante c'est maintenant E.
je remets Memorise à 0

1 2 3 4 Memorise
D 0 1 1 0 => 0
E 1 1 0 0 => 0
B 1 1 0 1 => 0
C 1 0 1 1 => 0

je vais comparer E à B et C.

1 2 3 4 Memorise
D 0 1 1 0 => 0
E 1 1 0 0 => 1
B 1 1 0 1 => 1
C 1 0 1 1 => 1

1 2 3 4 Memorise
D 0 1 1 0 => 0
E 1 1 0 0 => 2
B 1 1 0 1 => 2
C 1 0 1 1 => 1
Dans Memorise, je vois que E se trouve dans B, donc j'efface B et je remets Memorise à 0

1 2 3 4 Memorise
D 0 1 1 0 => 0
E 1 1 0 0 => 0
C 1 0 1 1 => 0

J'ai fini.
Ma question est de savoir si on peut améliorer cet algo : certainement d'ailleurs...

salut

si tu mémorise la position de la dernière colonne remplit et le nombre d’éléments égale à 1
cela te permettrais peut être d’accélérer le processus

Reprenons ton exemple

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
<div class="cms_table"><table width="500" class="cms_table"><tr valign="top" class="cms_table_tr"><td class="cms_table_td">Indice</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">2</td>
<td class="cms_table_td">3</td>
<td class="cms_table_td">4</td>
<td class="cms_table_td">Nb</td>
<td class="cms_table_td">Last Pos</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">D</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">2</td>
<td class="cms_table_td">3</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">E</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">2</td>
<td class="cms_table_td">2</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">A</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">3</td>
<td class="cms_table_td">3</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">B</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">3</td>
<td class="cms_table_td">4</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">C</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">3</td>
<td class="cms_table_td">4</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">F</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">3</td>
<td class="cms_table_td">3</td>
</tr>
</table></div>

on trie sur Nb,LastPos et ensuite les différente colonne te permettra déjà de gagner du temps dans tes boucles

ce qui nous donne

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
<div class="cms_table"><table width="500" class="cms_table"><tr valign="top" class="cms_table_tr"><td class="cms_table_td">Indice</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">2</td>
<td class="cms_table_td">3</td>
<td class="cms_table_td">4</td>
<td class="cms_table_td">Nb</td>
<td class="cms_table_td">Last Pos</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">E</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">2</td>
<td class="cms_table_td">2</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">D</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">2</td>
<td class="cms_table_td">3</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">A</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">3</td>
<td class="cms_table_td">3</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">F</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">3</td>
<td class="cms_table_td">3</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">C</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">3</td>
<td class="cms_table_td">4</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">B</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">3</td>
<td class="cms_table_td">4</td>
</tr>
</table></div>

le reste devient évident tu ne peut faire des test que de façon croissante
ne pas repartir du début pour savoir si il existe une solution passé car celle-ci sont impossible

Voici un bout de code, c'est du Windev, ça se lit comme du pseudo-code.

Testé, vérifié, Moins de 1seconde sur 1000 lignes et 20 colonnes.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
 
 
sst est une Structure 
	qnom est une chaîne
	qtb est un tableau de 20 booléens
	qcompteur est un entier
	qretenu est un entier 		// 0=En-attente , 1=retenu 2=doublon
	qpere est une chaîne        // nom de la ligne 'père' de cette ligne, uniquement en cas de doublon.
FIN
tb_sst est un tableau de 0 sst 
 
 
 
 
qsst est un sst
n, i , j , k est un entier 
b est un booléen
 
// Initialisation ********************************
n = 1000 
POUR i = 1 A n
	qsst.qnom = " nom:" + i
	k = 0
	POUR j = 1 A 20
		qsst.qtb[j] = Faux
		SI Hasard() > 0.5 ALORS 
			qsst.qtb[j] = Vrai 
			k++
		FIN
	FIN
	qsst.qcompteur = k
	qsst.qretenu = 0
	TableauAjoute(tb_sst, qsst)
 
FIN
 
//   FIN DE L'INITIALIQATION *************************************
 
TableauTrie(tb_sst, ttMembre,"qcompteur")
 
ch est une chaîne
doublon est un booléen
POUR i = 1 A n
	SI tb_sst[i].qretenu = 0 ALORS   // Si la ligne courante est en suspens, je la retiens.   et je regarde parmi les suivantes si certaines sont en doublon avec elle.
		tb_sst[i].qretenu = 1 
		POUR j = i+1 A n                                // Parmi les lignes suivantes
			SI tb_sst[i].qretenu = 0 ALORS      //  Je ne regarde que les lignes en suspens
				doublon = Vrai	
				POUR k =1 A 20                              
					SI tb_sst[i].qtb[k] = Vrai _ET_ tb_sst[j].qtb[k] = Faux ALORS 
						doublon = Faux                      // Dès que j'ai une colonne contre-exemple, la ligne ne fait pas doublon
						k = 21
					FIN
				FIN
				SI doublon ALORS                                   // Si la ligne J est en doublon avec I, je mets à jour qretenu et qpere     
					tb_sst[j].qretenu = 2
					tb_sst[j].qpere = "pere: " + i 
				FIN
			FIN
		FIN         //     POUR j = i+1 A n    
	FIN                 //   SI tb_sst[i].qretenu = 0 
 
        // Eventuellement, affichage de cet enregistrement 
        affiche(tb_sst[i] )
 
FIN   // i suivant

15/03/2017, 15h42
lepatantpato

Bonjour

Merci de ton code ; j'ai testé avec Windev le code; mais le résultat est=1 partout....
15/03/2017, 16h28
tbc92

Effectivement. Quand j'ai ajouté les commentaires dans le message, j'ai dû faire une bourde.
Ligne 48, c'est tb_sst[j] au lieu de tb_sst[i]

Citation:

Envoyé par anapurna

salut

si tu mémorise la position de la dernière colonne remplit et le nombre d’éléments égale à 1
cela te permettrais peut être d’accélérer le processus

Reprenons ton exemple

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
<div class="cms_table"><table width="500" class="cms_table"><tr valign="top" class="cms_table_tr"><td class="cms_table_td">Indice</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">2</td>
<td class="cms_table_td">3</td>
<td class="cms_table_td">4</td>
<td class="cms_table_td">Nb</td>
<td class="cms_table_td">Last Pos</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">D</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">2</td>
<td class="cms_table_td">3</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">E</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">2</td>
<td class="cms_table_td">2</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">A</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">3</td>
<td class="cms_table_td">3</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">B</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">3</td>
<td class="cms_table_td">4</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">C</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">3</td>
<td class="cms_table_td">4</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">F</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">3</td>
<td class="cms_table_td">3</td>
</tr>
</table></div>

on trie sur Nb,LastPos et ensuite les différente colonne te permettra déjà de gagner du temps dans tes boucles

ce qui nous donne

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
<div class="cms_table"><table width="500" class="cms_table"><tr valign="top" class="cms_table_tr"><td class="cms_table_td">Indice</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">2</td>
<td class="cms_table_td">3</td>
<td class="cms_table_td">4</td>
<td class="cms_table_td">Nb</td>
<td class="cms_table_td">Last Pos</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">E</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">2</td>
<td class="cms_table_td">2</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">D</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">2</td>
<td class="cms_table_td">3</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">A</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">3</td>
<td class="cms_table_td">3</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">F</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">3</td>
<td class="cms_table_td">3</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">C</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">3</td>
<td class="cms_table_td">4</td>
</tr>
<tr valign="top" class="cms_table_tr"><td class="cms_table_td">B</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">0</td>
<td class="cms_table_td">1</td>
<td class="cms_table_td">3</td>
<td class="cms_table_td">4</td>
</tr>
</table></div>

le reste devient évident tu ne peut faire des test que de façon croissante
ne pas repartir du début pour savoir si il existe une solution passé car celle-ci sont impossible

Oui, merci
je fais le tri sur Nb+les colonnes et j'améliore grandement la vitesse

16/03/2017, 10h37
tbc92

J'ai l'impression que tu n'as pas vu mon correctif :
ligne 48 , remplacer i par j.
16/03/2017, 10h53
lepatantpato

Oui, je l'ai vu. Cela fonctionne, merci; je compare ton algo avec le mien.
16/03/2017, 16h59
lepatantpato

A tbc92 :
ton algo devient plus rapide que le mien dès qu'on dépasse 20 colonnes.
Merci à tous.