JavaScriptでシーケンスから値のグループを削除できるすべてのパターンを求める方法

JavaScriptで、元のシーケンスの要素の順序を保ったまま(安定な状態で)、指定した値のグループをシーケンスから削除する方法が全部で何通りあるかを求める関数を作成します。ここでのルールは、削除対象の各値について、元のシーケンスから1つのインスタンスだけを削除するというものです。

問題の例

例として、次のシーケンス配列があるとします。

const arr = [1, 2, 1, 3, 1, 4, 4];

削除したい配列は以下の通りです。

const arr2 = [1, 4, 4];

要素の順序を崩すことなく削除を実行できる方法は、次の3通りあります。

1 --> [2, 1, 3, 1]
2 --> [1, 2, 3, 1]
3 --> [1, 2, 1, 3]

したがって、この関数はこれらのシーケンスに対して 3 を出力する必要があります。

解き方のアプローチ

この問題は、以下の4つのステップで効率的に解くことができます。

ステップ1: 各値の出現位置を記録する

まず、削除対象の各値が元の配列のどのインデックスに現れるかをすべて記録します。

ステップ2: 重複値の位置候補を調整する

削除対象に同じ値が複数含まれる場合(この例では「4」が2つ)、組み合わせの重複カウントを防ぐため、位置候補を前方と後方の両方向から絞り込みます。

ステップ3: 有効な組み合わせを再帰的に列挙する

各値の削除位置の候補の中から、インデックスが昇順になるような組み合わせを再帰的に生成します。

ステップ4: 結果を生成してカウントする

各組み合わせに従って実際に要素を削除した配列を作成し、その総数を返します。

コード例

const arr = [1, 2, 1, 3, 1, 4, 4];
const arr2 = [1, 4, 4];
const possibleRemovalCombinations = (original, part) => {
    const sorter = (a, b) => a - b;
    part.sort(sorter);
    let place = [];
    part.forEach(el => {
        place[el] = []
    });
    original.forEach((el, index) => {
        if(place[el]){
            place[el].push(index);
        }
    });
    let connection = part.map(el => place[el].slice());
    for(let i = 1; i < connection.length; i++){
        if (part[i - 1] != part[i]){
            continue;
        }
        let left = connection[i - 1][0];
        while(connection[i][0] <= left){
            connection[i].shift();
        };
    };
    for (let i = connection.length - 2; i >= 0; i--) {
        if(part[i] != part[i + 1]){
            continue;
        }
        let right = connection[i + 1][connection[i + 1].length - 1];
        while(connection[i][connection[i].length - 1] >= right){
            connection[i].pop();
        };
    };
    const combineArray = (step, prev, combination) => {
        for (let i = 0; i < connection[step].length; i++) {
            let curr = connection[step][i];
            if(prev >= curr && original[prev] == original[curr]){
                continue;
            }
            if(step + 1 == connection.length){
                combinations.push(combination.concat([curr]))
            }
            else {
                combineArray(step + 1, curr, combination.concat([curr]));
            };
        };
    };
    let combinations = [], res = [];
    combineArray(0, -1, []);
    for (let i = 0; i < combinations.length; i++) {
        let copy = original.slice();
        combinations[i].forEach(el => delete copy[el]);
        res[i] = copy.filter(el => el !== undefined);
    };
    return res.length;
};
console.log(possibleRemovalCombinations(arr, arr2));

出力

コンソールには次のように出力されます。

3

まとめ

このアルゴリズムでは、削除対象の値ごとに出現位置を整理し、重複する組み合わせを除外しながら再帰的に探索することで、順序を保った削除パターンの総数を正確に求めることができます。同じ値が配列内に複数回現れるケースでも、位置候補を事前に調整しておくことで重複カウントを防げる点がポイントです。