マルチセットのすべてのパーティションを見つける方法。JavaScriptで各部分に個別の要素があります。

そのような配列があるとしましょう-

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

配列全体に追加されるすべての組み合わせを検出し、要素が繰り返されないようにするためのアルゴリズムを作成する必要があります。

組み合わせの例-

[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]]