एक मल्टीसेट के सभी विभाजन कैसे खोजें, जहां प्रत्येक भाग में जावास्क्रिप्ट में अलग-अलग तत्व हों

मान लें कि हमारे पास ऐसा सरणी है -

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]

स्पष्टीकरण

[ए, बी, सी] [ए, बी, सी] [डी, ई] और [ए, बी, सी] [डी, ई] [ए, बी, सी] एक ही संयोजन हैं। साथ ही, सबसेट के साथ क्रम भी मायने नहीं रखता।

उदाहरण के लिए - [ए, बी, सी] और [बी, ए, सी] समान होना चाहिए।

उदाहरण

इसके लिए कोड होगा -

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