জাভাস্ক্রিপ্টে মাল্টিসেটের সব পার্টিশন খুঁজে বের করা যেখানে প্রতিটি অংশে স্বতন্ত্র উপাদান থাকে

মান লিয়ে, আমাদের নিচের মত একটি অ্যারে আছে -

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