JavaScriptでアナグラム配列同士のインデックスをマッピングする方法

アナグラム配列とは

ある配列の要素を並べ替えることで、もう一方の配列とまったく同じ並びを作れる場合、その2つの配列は「互いのアナグラム」であると言えます。

例えば、次のような関係です。

[1, 2, 3] と [2, 1, 3] は互いにアナグラムです。

ここで、互いにアナグラムの関係にある2つの配列 arr1 と arr2 が与えられたとします。

求められているのは、この2つの配列を受け取り、arr1 と同じ長さの新しい「マッピング配列」を返すJavaScript関数です。マッピング配列には、arr1 の各要素が arr2 のどのインデックス位置に存在するかを格納します。

入力例

例えば、入力が次の2つの配列だった場合:

const arr1 = [23, 39, 57, 43, 61];
const arr2 = [61, 23, 43, 57, 39];

出力は次のようになります。

const output = [1, 4, 3, 2, 0];

これは、arr1 のインデックス0にある要素(23)が arr2 ではインデックス1に位置し、インデックス1にある要素(39)は arr2 のインデックス4に位置する――といった対応関係を表しています。以降も同様に、すべての要素について位置関係が記録されます。

実装例

最もシンプルなのは、二重ループで各要素の位置を探す方法です。

const arr1 = [23, 39, 57, 43, 61];
const arr2 = [61, 23, 43, 57, 39];
const anagramMappings = (arr1 = [], arr2 = []) => {
    const res = [];
    for(let i = 0; i < arr1.length; i++) {
        for(let j = 0; j < arr2.length; j++) {
            if(arr1[i] == arr2[j]){
                res.push(j);
            };
        };
    };
    return res;
};
console.log(anagramMappings(arr1, arr2));

より簡潔な書き方(map + indexOf)

Array.prototype.map() と indexOf() を組み合わせると、同じ処理を1行で表現できます。

const anagramMappings = (arr1 = [], arr2 = []) =>
    arr1.map(el => arr2.indexOf(el));

さらに、要素数が多い配列に対しては、Map を使って arr2 の値とインデックスを事前に登録しておくことで、計算量 O(n²) の二重ループを O(n) まで高速化できます。

const anagramMappings = (arr1 = [], arr2 = []) => {
    const indexMap = new Map();
    arr2.forEach((val, idx) => indexMap.set(val, idx));
    return arr1.map(el => indexMap.get(el));
};

出力結果

いずれの方法でも、コンソールには次のように出力されます。

[ 1, 4, 3, 2, 0 ]