Cách tìm tất cả các phân vùng của một tập hợp nhiều người, trong đó mỗi phần có các phần tử riêng biệt trong JavaScript

Giả sử chúng ta có một mảng như vậy -

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

Chúng tôi được yêu cầu tạo một thuật toán để nó sẽ tìm tất cả các tổ hợp cộng lại cho toàn bộ mảng, trong đó không phần tử nào được lặp lại.

Các kết hợp mẫu -

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

Giải thích

[A, B, C] [A, B, C] [D, E] và [A, B, C] [D, E] [A, B, C] là những tổ hợp giống nhau. Ngoài ra, thứ tự với các tập hợp con cũng không quan trọng.

Ví dụ - [A, B, C] và [B, A, C] phải giống nhau.

Ví dụ

Mã cho điều này sẽ là -

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));

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

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