c# - 2 つのリスト間のシーケンスの違いを評価するアルゴリズム

Question

2 つのシーケンスを比較するアルゴリズムを探しています。

シーケンス A - 最適な順序の整数 ID のリストになります

シーケンス B - 同じ ID のリストになりますが、順序が異なる場合があります。

2 つのリストの順序の違いを検出したいと考えています。

そのため、これを行うアルゴリズムを探しています。これが以前に解決された一般的な問題であるかどうか疑問に思っています

Answer 1

それらがどの程度異なるかを測定したいが、違いがどこで発生するかは気にしない場合は、Kendall の相関係数を使用できます。-1 (リストの順序が逆) から +1 (リストの順序が同じ) までのスコアが表示されます。

基本的に、両方のリストで同じ順序になっている要素のペアの数をカウントし、ペアの総数で割ります。

int[] a = { 1, 2, 3, 4, 5, 6, 7, 8 };
int[] b = { 3, 4, 1, 8, 6, 7, 2, 5 };

double numer = 0;
for (int i = 0; i < (a.Length - 1); i++)
  for (int j = i + 1; j < a.Length; j++)
    numer += Math.Sign(a[i] - a[j]) * Math.Sign(b[i] - b[j]);

double tau = numer / (a.Length * (a.Length - 1) / 2);