1. #1
    Membre régulier
    Homme Profil pro
    Développeur informatique
    Inscrit en
    février 2012
    Messages
    133
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Enseignement

    Informations forums :
    Inscription : février 2012
    Messages : 133
    Points : 85
    Points
    85

    Par défaut 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.

  2. #2
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 403
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 403
    Points : 2 956
    Points
    2 956

    Par défaut

    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.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  3. #3
    Membre régulier
    Homme Profil pro
    Développeur informatique
    Inscrit en
    février 2012
    Messages
    133
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Enseignement

    Informations forums :
    Inscription : février 2012
    Messages : 133
    Points : 85
    Points
    85

    Par défaut 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...

  4. #4
    Membre expert
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 447
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 447
    Points : 3 844
    Points
    3 844

    Par défaut

    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 : 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
    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
    Indice 1 2 3 4 Nb Last Pos
    D 0 1 1 0 2 3
    E 1 1 0 0 2 2
    A 1 1 1 0 3 3
    B 1 1 0 1 3 4
    C 1 0 1 1 3 4
    F 1 1 1 0 3 3
    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 : 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
    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
    Indice 1 2 3 4 Nb Last Pos
    E 1 1 0 0 2 2
    D 0 1 1 0 2 3
    A 1 1 1 0 3 3
    F 1 1 1 0 3 3
    C 1 0 1 1 3 4
    B 1 1 0 1 3 4

    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
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  5. #5
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 403
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 403
    Points : 2 956
    Points
    2 956

    Par défaut

    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 windev : 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
    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
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  6. #6
    Membre régulier
    Homme Profil pro
    Développeur informatique
    Inscrit en
    février 2012
    Messages
    133
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Enseignement

    Informations forums :
    Inscription : février 2012
    Messages : 133
    Points : 85
    Points
    85

    Par défaut

    Bonjour

    Merci de ton code ; j'ai testé avec Windev le code; mais le résultat est=1 partout....

  7. #7
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 403
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 403
    Points : 2 956
    Points
    2 956

    Par défaut

    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]
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  8. #8
    Membre régulier
    Homme Profil pro
    Développeur informatique
    Inscrit en
    février 2012
    Messages
    133
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Enseignement

    Informations forums :
    Inscription : février 2012
    Messages : 133
    Points : 85
    Points
    85

    Par défaut

    Citation Envoyé par anapurna Voir le message
    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 : 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
    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
    Indice 1 2 3 4 Nb Last Pos
    D 0 1 1 0 2 3
    E 1 1 0 0 2 2
    A 1 1 1 0 3 3
    B 1 1 0 1 3 4
    C 1 0 1 1 3 4
    F 1 1 1 0 3 3
    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 : 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
    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
    Indice 1 2 3 4 Nb Last Pos
    E 1 1 0 0 2 2
    D 0 1 1 0 2 3
    A 1 1 1 0 3 3
    F 1 1 1 0 3 3
    C 1 0 1 1 3 4
    B 1 1 0 1 3 4

    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

  9. #9
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 403
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 403
    Points : 2 956
    Points
    2 956

    Par défaut

    J'ai l'impression que tu n'as pas vu mon correctif :
    ligne 48 , remplacer i par j.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  10. #10
    Membre régulier
    Homme Profil pro
    Développeur informatique
    Inscrit en
    février 2012
    Messages
    133
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Enseignement

    Informations forums :
    Inscription : février 2012
    Messages : 133
    Points : 85
    Points
    85

    Par défaut

    Oui, je l'ai vu. Cela fonctionne, merci; je compare ton algo avec le mien.

  11. #11
    Membre régulier
    Homme Profil pro
    Développeur informatique
    Inscrit en
    février 2012
    Messages
    133
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Enseignement

    Informations forums :
    Inscription : février 2012
    Messages : 133
    Points : 85
    Points
    85

    Par défaut

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

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 0
    Dernier message: 27/02/2015, 11h41
  2. [DeskI V5-V6] Calculer des sous totaux dans un tableau croisé dynamique
    Par Tancredoc dans le forum Débuter
    Réponses: 17
    Dernier message: 09/06/2010, 14h22
  3. Extraire des sous ensembles de BOOST
    Par MenshaKaine dans le forum Boost
    Réponses: 5
    Dernier message: 22/12/2009, 11h14
  4. Extraire des Subarrays contenus dans un Tableau
    Par fabricekenk dans le forum LabVIEW
    Réponses: 14
    Dernier message: 07/09/2009, 14h18

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo