JavaScriptでマルチセットのすべての分割（パーティション）を見つける方法 ― 各部分集合に重複要素がない場合

問題の概要

たとえば、次のような配列があるとします。

const arr = [A, A, B, B, C, C, D, E];

ここで必要なのは、配列の全要素をちょうど一度ずつ使い切るような「分割（パーティション）」をすべて列挙するアルゴリズムです。ただし、各部分集合の中に同じ要素が2回以上現れてはいけません。

組み合わせの例は次のとおりです。

[A, B, C, D, E] [A, B, C]
[A, B, C, D] [A, B, C, E]
[A, B, C] [A, B, C] [D, E]

条件の整理

[A, B, C] [A, B, C] [D, E] と [A, B, C] [D, E] [A, B, C] は、部分集合の並び順が異なるだけで、同じ分割とみなします。部分集合同士の順序は結果に影響しません。

同様に、部分集合内部の要素の順序も無視します。たとえば [A, B, C] と [B, A, C] は同じものとして扱います。

実装コード

これを実現するコードは次のとおりです。

const arr = [['A', 1], ['B', 2], ['C', 3]];
const spread = (arr, ind, combination) => {
    if (arr[1] === 0)
    return [combination];
    if (ind === −1)
    return [combination.concat([arr])];
    let result = [];
    for (let c=1; c<=Math.min(combination[ind][1], arr[1]); c++){
        let comb = combination.map(x => x.slice());
        if (c == comb[ind][1]){
            comb[ind][0] += arr[0];
        } else {
            comb[ind][1] −= c;
            comb.push([comb[ind][0] + arr[0], c]);
        }
        result = result.concat(spread([arr[0], arr[1] − c], ind − 1, comb));
    }
    let comb = combination.map(x => x.slice());
    return result.concat(spread(arr, ind − 1, comb));
};
const helper = arr => {
    function inner(ind){
        if (ind === 0)
        return [[arr[0]]];
        const combs = inner(ind − 1);
        let result = [];
        for (let comb of combs)
        result = result.concat(
        spread(arr[ind], comb.length − 1, comb));
        return result;
    }
    return inner(arr.length − 1);
};
const returnPattern = (arr = []) => {
    const rs = helper(arr);
    const set = new Set();
    for (let r of rs){
        const _r = JSON.stringify(r);
        if (set.has(_r))
        console.log('Duplicate: ' + _r);
        set.add(_r);
    }
    let str = '';
    for (let r of set)
    str += '\n' + r
    str += '\n\n';
    return str;
};
console.log(returnPattern(arr));

出力結果

コンソールへの出力は次のようになります。

[["ABC",1],["BC",1],["C",1]]
[["AB",1],["BC",1],["C",2]]
[["ABC",1],["B",1],["C",2]]
[["AB",1],["B",1],["C",3]]
[["AC",1],["B",1],["BC",1],["C",1]]
[["A",1],["B",1],["BC",1],["C",2]]
[["AC",1],["BC",2]]
[["A",1],["BC",2],["C",1]]
[["AC",1],["B",2],["C",2]]
[["A",1],["B",2],["C",3]]

アルゴリズムのポイント

この実装では、要素の種類を1つずつ処理しながら、その要素を「既存の部分集合に統合する」か「独立した新しい部分集合として追加する」かを再帰的に試します。これにより、全要素を過不足なく使い切るすべての分割パターンを網羅的に生成できます。

出力では、各部分集合は連結された文字列で表されます。たとえば ["ABC",1] は A・B・C を含む部分集合が1個あることを意味し、["C",3] は [C] という部分集合が3個あることを示します。

最終段階では JSON.stringify で各結果を文字列化し、Set を使って重複を排除しています。これにより、順序の違いによる重複を取り除き、一意な分割だけを出力できます。