Creating An Array Of Unique Combinations

I have an array of components: let components = ['a', 'b', 'c']; It is possible to combine those components to make products; i.e., 'a' + 'b' = 'ab'. I have a catalog of possible

Solution 1:

Is below code satisfy you requirement?

1. Shuffle the components array as many as posible;
2. Use array's splice function to splice with length of requires;

let components = ["a", "b", "c", "d", "e", "f"];

function getCatalogProducts(components: string[], requires: number) {
  if (components.length < requires) return [];

  if (components.length === requires) return [components];

  let results: string[] = [];
  let cloneComponents = [...components];
  while (cloneComponents.length) {
    let cur = cloneComponents.splice(0, requires);
    let curStr = cur.sort().join('');
    results.push(curStr);
  }

  return results;
}

let shuffleComponentsArray = permute(components);

console.clear();
let results: any = [];
for (let i = 0; i < shuffleComponentsArray.length; i++) {
  let posibleCatalogProducts = getCatalogProducts(shuffleComponentsArray[i], 2);
  if (!results.some((item: any) => posibleCatalogProducts.sort().join('') === item.sort().join(''))) {
    results.push(posibleCatalogProducts);
  }
}

console.log(results);


// Below 3 functions are shuffle array related

function swap(arr: any, a: number, b: number) {
  var temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

function factorial(n: number) {
  var val = 1;
  for (var i = 1; i < n; i++) {
    val *= i;
  }
  return val;
}

function permute(perm: any) {
  let results = [];
  var total = factorial(perm.length);

  for (var j = 0, i = 0, inc = 1; j < total; j++, inc *= -1, i += inc) {

    for (; i < perm.length - 1 && i >= 0; i += inc) {
      results.push([...perm]);
      swap(perm, i, i + 1);
    }

    results.push([...perm]);

    if (inc === 1) {
      swap(perm, 0, 1);
    } else {
      swap(perm, perm.length - 1, perm.length - 2);
    }
  }

  return results;
}

Solution 2:

Edited to accommodate the needs in your comment. This example uses a fairly straight forward recursive function to generate all unique combinations with the option to limit the maximum combination size (used to generate the catalog with only combinations of size 2).

The possibleProducts are a filtered array of all the unique combinations generated by passing the catalog array to the same function with no limits.

// generates unique combinations recursively
function combineRec(array, size, limit = false) {
  array = array.map(e => [e]);
  // max size of combinations.
  size = size || array.length;
 
  const acc =[];
  
  const spread = (s, arr) => arr.forEach((e, i, a) => {
    let 
      seed = [...s, ...e],
      segment = a.slice(i + 1);
    acc.push([...s, ...e]);
    if (s.length < size - 1 && segment.length > 0) {
      spread(seed, segment);
    }
  });

  array.forEach((e, i, a) => (
    spread(e, a.slice(i + 1))
  ))

  // if limit is true return only combinations of specified size.
  return r = limit ? acc.filter(({ length }) => length === size) : acc;
}

// filters out combinations with duplicate elements
const filterByElements = (array) => array.filter(arr =>
  !arr.some((a, i) => a.some(e => arr.slice(i + 1).flat().includes(e)))
);

const components = ['a', 'b', 'c', 'd', 'e', 'f'];

// generate catalog (return only combinations of 2)
let catalog = combineRec(components, 2, true);

// generate all possible catalog combinations (returns all)
let catalogCombinations = combineRec(catalog);

// filter to exlude duplicates and map combination arrays to strings.
let possibleProducts = filterByElements(catalogCombinations)
  .sort((a, b) => a.length - b.length)
  .map(p => p.map(c => c.join('')));

console.log('catalog: ', JSON.stringify(catalog));
console.log('possibleProducts: ', JSON.stringify(possibleProducts));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Solution 3:

In addition to the other solution, with this one, you can adjust the size of the products. (Assuming that COMPONENTS % SIZE_OF_EACH_PRODUCT === 0, in this case).

const COMPONENTS = ["a", "b", "c", "d", "e", "f", "g", "h", "i"];
const SIZE_OF_EACH_PRODUCT = 3;

const getCombinations = (inputArr, r) => {
  const res = [];
  const f = (inputArr, tmpArr, r, inputIndex, tmpIndex) => {
    if (tmpIndex == r) {
      let s = [];
      for (let x = 0; x < r; x++) s.push(tmpArr[x]);
      res.push(s);
      return;
    }
    if (inputIndex >= inputArr.length) return;
    tmpArr[tmpIndex] = inputArr[inputIndex];

    f(inputArr, tmpArr, r, inputIndex + 1, tmpIndex + 1);
    f(inputArr, tmpArr, r, inputIndex + 1, tmpIndex);
  };
  f(inputArr, [], r, 0, 0);
  return res;
};

const catalog = getCombinations(COMPONENTS, SIZE_OF_EACH_PRODUCT);

const uniqueCombinations = getCombinations(catalog, COMPONENTS.length / SIZE_OF_EACH_PRODUCT).filter((arrays) => {
  for (let i = 0; i < arrays.length; i++)
    for (let u = 0; u < arrays.length; u++) 
      if (!(i === u))
        if (arrays[i].some((char) => arrays[u].includes(char))) return false;
  return true;
});

console.log(uniqueCombinations);

Solution 4:

Based on your other recent related question, I think I understand that what you want would be for something like this:

const catalog= ["ad", "aab", "ace", "cd", "ba", "bd", "adf", "def"]
const components = ["a", "b", "a", "c", "d", "e"]

simultaneousItems (catalog, components) 

to yield

[["ad", "ace"], ["ad", "ba"], ["aab", "cd"], ["ace", "ba"], ["ace", "bd"], ["cd", "ba"]]

where every array in the result is a maximal subset of catalog items that can be made together out of the components supplied. So, for instance, none of the output arrays contains "adf" or "def", since we have no "f" in the components, and none of them contain both "ad" and "aab" since we only have two "a"s in the component list.

If this is correct, then the following snippet would seem to do. The code explanation in that answer serves for this, with two modifications:

• The collect function is simplified here to a more logical core

• The wrapper simultaneousItems is altered to split the input strings into arrays and joint back the output ones. And it no longer has to handle extracting the values from your itemCatalog format.

const dropFirst = (x, xs, i = xs .indexOf (x)) =>
  i < 0 ? [... xs] : [... xs .slice (0, i), ... xs .slice (i + 1)]

const dropEach = ([x, ...xs], ys) => 
  x == undefined ? ys : dropEach (xs, dropFirst (x, ys))

const canMake = ([c, ...cs], comps) => 
  c == undefined ? true : comps .includes (c) ? canMake (cs, dropFirst (c, comps)) : false

const isSubset = (xs, ys) =>
  xs .every (x => ys .includes (x))

const maximize = (xs) => 
  xs .filter (x => ! (xs .some (y => x !== y && isSubset (x, y))))

const collect = ([x, ...xs], ys) => 
  x == undefined
    ? [[]]
  : canMake (x, ys)
    ? [
        ... collect (xs, dropEach (x, ys)) .map (coll => [x, ... coll]), 
        ... collect (xs, ys)
      ]
    : collect (xs, ys)

const simultaneousItems = (catalog, components) => 
  maximize (collect (catalog .map (s => s .split ('')), components)) 
    .map (g => g .map (ss => ss .join ('')))


const catalog = ["ad", "aab", "ace", "cd", "ba", "bd", "adf", "def"]

const components = ["a", "b", "a", "c", "d", "e"]

console .log (
  simultaneousItems (catalog, components)
)

.as-console-wrapper {max-height: 100% !important; top: 0}