Discussion :

[nahoula1231]

Bonjour,
j'ai deux vecteurs V1 et V2 d'éléments labélisés par des lettres alphabétiques.
Je souhaite trouver les différentes correspondances entre les éléments du premier vecteur avec un élément du deuxième vecteur sachant qu'on correspond que les éléments ayant un même label.

EXEMPLE :
V1= [A,B,C1,C2]
V2= [A1,A2,B,C1,C2,D]
Correspondances:
A-A1,B-B,C1-C1,C2-C2
A-A1,B-B,C1-C2,C2-C1
A-A2,B-B,C1-C1,C2-C2
A-A2,B-B,C1-C2,C2-C1

Je n'arrive pas à trouver un algorithme qui me fait ça
Any help ? merci

[tbc92]

Bonsoir,

Pour être sur que le besoin soit clairement défini, imaginons le jeu de données :
V1= [A,B,C1,C2,E]
V2= [A1,A2,B,C1,C2,D]
E n'a pas d'enfant dans le 2ème tableau, et donc il n'y a aucune solution.
C'est correct ?


Deuxième question
Dans ton exemple, tu n'as pas retenu les 4 solutions ci-dessous :
A-A1,B-B,C1-C1,C2-C1
A-A1,B-B,C1-C2,C2-C2
A-A2,B-B,C1-C1,C2-C1
A-A2,B-B,C1-C2,C2-C2

C'est volontaire ou c'est un oubli ?

[nahoula1231]

Bonjour,

Oui c'est exactement ça. On veut correspondre tous les éléments du V1

Pour être sur que le besoin soit clairement défini, imaginons le jeu de données :
V1= [A,B,C1,C2,E]
V2= [A1,A2,B,C1,C2,D]
E n'a pas d'enfant dans le 2ème tableau, et donc il n'y a aucune solution.
C'est correct ?

Ici, c'est volontaire. On ne peut correspondre un élément du V1 qu'à un seul élément de V1 !

Deuxième question
Dans ton exemple, tu n'as pas retenu les 4 solutions ci-dessous :
A-A1,B-B,C1-C1,C2-C1
A-A1,B-B,C1-C2,C2-C2
A-A2,B-B,C1-C1,C2-C1
A-A2,B-B,C1-C2,C2-C2

C'est volontaire ou c'est un oubli ?

[kolodz]

Je vais poser des question stupide :

Supposons les deux vecteurs suivants :

V1 =[A,B]
V2 =[B,A]

Quel est la correspondance supposé ?

A-A, B-B
B-B
A-A

Cela pose deux questions sur le comportement le l'algorithme.
1. La correspondance doit-elle ordonnée dans V2 ?
2. Si la correspondance doit-être ordonnée quel est la priorité ? (L'ordre de V1 ou l'ordre de V2 ?)

Supposons les deux vecteurs suivants :

V1 =[Aa,B,Ab]
V2 =[A1,A2,A3,A4,B,A5]

L'une des correspondances suivantes est-t-elle possible ?

Aa-A5
Aa-A5, B-B
B-B, Aa-A5,

(Les variations sont dû aux questions précédents.)
L'idée est de savoir si il est nécessaire d'avoir le maximum de match ou si il est possible d'avoir des correspondances avec moins de matchs.

Cordialement,
Patrick Kolodziejczyk.

[nahoula1231]

Bonjour,

L'idée ici est de matcher tous les éléments de V1, en supposant qu'on a déjà fait un test qui vérifie que à chaque élément de V1 on a 1 ou plusieurs possibles correspondants dans V2.

[ternel]

Si tes vecteurs sont triés, il suffit de faire un parcours simultané.

Regarde les exemples de std::merge sur cppreference.com pour avoir des idées.