Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Tester si un vecteur est un sous ensemble d'un autre vecteur


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau membre du Club
    Tester si un vecteur est un sous ensemble d'un autre vecteur
    bonjour;
    j'ai une matrice de taille (n*m) de type binaire (0, 1)
    deux vecteurs ligne sont similaire si un vecteur ligne est un sous ensemble d'un autre vecteur ligne

    je veux écrire un algorithme qui permet de vérifier si deux vecteurs ligne sont similaire ou non
    exemple:


    voici l'algorithme que j'ai creer:

    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
     
    pour i=1 à n faire
      pour j=i+1 à n faire
          pour k=1 à m faire
           si (V[i,k]==1) alors
                d=d+1
               si(V[j,k]==1) alors
                    R=R+1
               finsi
          finsi
     
         finpour
      finpour
     
       si (d>R) alors
            v[j] est inclu dans V[i]
       sinon
            V[i] est inclu dans V[j]
       finsi
    finpour


    le probleme me que je rencontre dans le cas où par exemple si (V[1,4]=0, V[2,4]=1) et (V[1,4]=1, V[2,4]=0)

    aussi l'utilisation de la fonction booleene


    merci d'avance

  2. #2
    Rédacteur/Modérateur

    Je n'ai pas compris la question, mais voici déjà quelques corrections :

    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
     
    pour i=1 à n faire
      pour j=i+1 à n faire
          d=0  // Ajouté
          R=0  // Ajouté  
          pour k=1 à m faire
           si (V[i,k]==1) alors
                d=d+1
               si(V[j,k]==1) alors
                    R=R+1
               finsi
          finsi
     
         finpour k 
     
       si (d>R) alors
            v[j] est inclu dans V[i]
       sinon
            V[i] est inclu dans V[j]
      finsi
     finpour j  // Déplacé.
    finpour i


    Quand tu commences le traitement d'un couple i,j), il faut remettre à 0 toutes les variables. Sinon, ce que tu calcules, ce n'est pas la comparaison de i et j , c'est la comparaison de plein de colonnes avec plein d'autres colonnes.

    Et à la fin, pour afficher le bilan de la comparaison de i et j, il faut le faire au bon endroit.
    Là où tu l'avais mis, il y avait un bilan pour chaque valeur de i ; n bilans seulement, alors qu'il en faut beaucoup plus.
    Pour la lisibilité, j'ai mis Finpour i au lieu de Finpour.

    Sur le reste, je ne suis pas d'accord non plus, mais je ne sais pas trop ce que tu veux faire, donc j'ai un vague doute.
    Dans ce que tu fais, tu as forcément soit i inclus dans j, soit j inclus dans i. Et à mon avis, il y a aussi des cas où on n'a ni l'un ni l'autre.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  3. #3
    Membre éclairé
    Interval
    Bonjour,

    Sans rentrer dans le fond du sujet la première boucle devrait s'arrêter à n-1.
    Certes dans beaucoup de langages la deuxième boucle ne sera pas exécutée si l'indice de début est supérieur à l'indice de fin.
    Mais dans un algorithme (ie sans hypothèse de langage) cette supposition n'a pas lieu d'être.

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  4. #4
    Membre éclairé
    Economie de variabless
    Bonjour,

    Par ailleurs, sauf erreur de ma part, la réponse ne peut être systématiquement une inclusion. Exemple 0b11101000 et 10000111 ne sont pas inclus dans un sens ou l'autre.

    En fait c'est assez simple, il suffit de créer un vecteur temporaire Vtmp := V(i) & V(j) (& pour un ET binaire bit à bit qui peut se traduire - mal - par Vtmp(k) := v(i,k) * v(j,k) ).

    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    Si Vtmp == V(i) alors V(i) inclus dans V(j) sinon si Vtmp == V(j) alors V(j) inclus dans V(i) sinon pas d'inclusion


    C'est certainement la solution la plus simple si les vecteurs élémentaires sont représentés par des entiers dont chaque bit est un élément du vecteur.

    Sinon il est peut être plus efficace de travailler avec un flag F à 4 valeurs ; -1 pour i dans j, 0 pour i = j, 1 pour j dans i, 2 pour i et j sans relation. La boucle la plus interne devient :
    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
    F = 0
    pour k = 1 à m faire
       si v(i,k) > v(j,k) alors
          si F == -1 alors
             F = 2
             fin de boucle // break
          sinon
             F = 1
          fin_si
       sinon si v(i,k) < v(j,k) alors
          si F == 1 alors
             F = 2
             fin de boucle // break
          sinon
             F = -1
          fin_si
       fin_si


    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)