Discussion :

[Seabirds]

Bonjour à toutes et à tous ! Pour certaines raison, j'ai besoin de calculer une distance entre deux partitions.
Soit le vecteur v : {184, 184, 184, 170, 184, 170}. C'est le vecteur de référence qu'on va comparer à d'autres vecteurs de même taille, avec des critères de similarité un peu exotiques. Notamment, on ne s'intéresse pas aux valeurs exactes, sinon à la structure du vecteur (sous-groupes de valeurs).

Soit deux vecteurs de même "structure", leur distance à v doit être égale à 0 :
{1, 1, 1, 2, 1, 2}
{2, 2, 2, 1, 2, 1}
etc...

Plus tricky, on a le droit de scinder un groupe en plusieurs. La distance doit ici aussi être de 0
{1, 1, 1, 2, 3, 2} <- remarquez le 3 qui prend la place d'un 184 de v, ça c'est autorisé.
{1, 1, 3, 2, 3, 2} <- on peut d'ailleurs étendre le 3 à d'autres cases, du moment que ça prend la place d'un 184
{1, 3, 3, 2, 3, 2}

Par contre si il y a mismatch entre groupe, là ça ne va plus : l'indice 3 sert à faire référence à la fois à la valeur 170 et à la valeur 184 de v :
{184, 184, 184, 170, 184, 170}
{1, 1, 3, 3, 1, 3} distance à v = 1
{1, 3, 3, 3, 1, 3} distance à v = 2

Mon background de maths étant un peu limité, je ne sais pas mieux formaliser ce que je veux faire, je m'en excuse.
L'idée est d'avoir un algo qui mesure cette distance, auriez-vous entendu parler d'algo de ce genre en C++ ? N'hésitez pas à me dire à quoi ça vous fait penser, j'irai gratter de ce côté Ce n'est pas un devoir à rendre demain, c'est plutôt une demande d'aiguillage en terra incognita pour éviter de devoir ré-inventer la roue (en plus moche)

Merci d'avance !

[ternel]

Le problème est précisément que si tu ne sais pas le formaliser clairement, tu ne pourras pas l'expliciter assez dans un langage de programmation.

quelle est la formule de la distance entre deux vecteurs?

Tu peux commencer par calculer si deux vecteurs sont à la même distance.

En reprenant tes vecteurs d'exemple.

1. {184, 184, 184, 170, 184, 170}
2. {1, 1, 3, 3, 1, 3} distance à v = 1
3. {1, 3, 3, 3, 1, 3} distance à v = 2

Tu peux utiliser une (unsorted-)map ou un vector pour servir de traduction.
l'idée, c'est de tout linéariser de la même manière:
Chaque nombre est remplacé par son indice dans une liste des valeurs distinctes

1. {184, 170}, {0, 0, 0, 1, 0, 1}
2. {1, 3}, {0, 0, 1, 1, 0, 1}
3. {1, 3}, {0, 1, 1, 1, 0, 1}

Par contre, un soucis apparaitra s'il y a des permutations:
le vecteur {170, 184, 184, 170, 184, 170} apparaitra comme {170, 184}, {0, 1, 1, 0, 1, 0} de distance apparente 5, au lieu de simplement {184, 170}, {1, 0, 0, 1, 0, 1} de distance 1

Il faudra alors pouvoir procéder à des permutations dans l'ordre de traduction pour mesurer la distance minimale.

La distance en elle-même pourrait être la distance de Hamming une fois la bonne traduction faite.

[Seabirds]

Super merci beaucoup pour l'idée d'implémentation

Je n'avais pas entendu parler de la distance de Hamming, j'étais parti sur l'indice de Rand, l'indice de Jaccard, l'indice de Walalce et l'indice normalisé de Lermann, pour finalement voir que la variation d'information avait des propriétés assez intéressantes

Je regarde de plus près ce fameux Hamming
Merci encore !