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

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

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

  letresults: 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();
letresults: 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 relatedfunctionswap(arr: any, a: number, b: number) {
  var temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

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

functionpermute(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 recursivelyfunctioncombineRec(array, size, limit = false) {
  array = array.map(e => [e]);
  // max size of combinations.
  size = size || array.length;
 
  const acc =[];
  
  constspread = (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 elementsconstfilterByElements = (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).

constCOMPONENTS = ["a", "b", "c", "d", "e", "f", "g", "h", "i"];
constSIZE_OF_EACH_PRODUCT = 3;

constgetCombinations = (inputArr, r) => {
  const res = [];
  constf = (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))) returnfalse;
  returntrue;
});

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.

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

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

constcanMake = ([c, ...cs], comps) => 
  c == undefined ? true : comps .includes (c) ? canMake (cs, dropFirst (c, comps)) : falseconstisSubset = (xs, ys) =>
  xs .every (x => ys .includes (x))

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

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

constsimultaneousItems = (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}