C++で2つの配列間の互換性の差を求める方法

問題の概要

2人の友人が、お互いの相性を確かめたいと考えています。そこで、1からnまでの番号が付けられた映画を、それぞれが好みに応じてランク付けします。このとき求めるのが、2人の間の「互換性の差」です。

互換性の差とは、同じ映画に対する2人の相対的な順位付けがどれだけ食い違っているかを表す数値のことです。たとえば、A = [3, 1, 2, 4, 5]、B = [3, 2, 4, 1, 5] という2つの順位リストが与えられた場合、出力は 2 になります。これは、友人Aが映画1を映画2や4よりも上位にランク付けしている一方で、友人Bはそれらより下位にランク付けしているためです。

アルゴリズムの考え方

この問題を解くには、両方の配列を走査しながら次の手順を実行します。

• 現在の位置にある要素が一致している場合は、何もしません。
• 一致していない場合は、配列Bの中で A[i] と同じ値が現れる位置 j を探します。
• 見つけた B[j] を、隣接する要素と入れ替えながら位置 i まで1つずつ移動させ、その入れ替え回数をカウントします。

こうして求まった入れ替えの総回数が、2つの配列間の互換性の差となります。

サンプルコード

#include<iostream>
using namespace std;

int getArrayDiff(int A[], int B[], int n) {
    int result = 0;

    for (int i = 0; i < n; i++) {
        if (A[i] != B[i]) {

            int j = i + 1;
            while (A[i] != B[j])
                j++;

            while (j != i) {
                swap(B[j], B[j - 1]);
                j--;
                result++;
            }
        }
    }
    return result;
}

int main() {
    int A[] = { 3, 1, 2, 4, 5 };
    int B[] = { 3, 2, 4, 1, 5 };
    int n = sizeof(A)/sizeof(A[0]);

    cout << "Compatibility difference: " << getArrayDiff(A, B, n);
}

実行結果

Compatibility difference: 2