javascript - 创建一组独特的组合

Question

我有一组组件:

let components = ["a", "b", "c"];

可以将这些组件组合起来制造产品；即， "a" + "b" = "ab" .
我有一个可能的产品目录:

let catalog = ["ab", "ac", "bc"];

使用 lodash 之类的东西，我们可以创建一系列可能的产品。输出数组看起来像 ["ab", "ac", "bc"] .
但问题是，并非所有这些产品都可以构建，因为一旦使用了其中一个组件，它就无法再用于需要它的其他产品中。
我需要一个只显示可能结果的输出。当只有 3 个组件，而每个目录产品都需要 2 个时，显然一次创建多个产品是不可能的。因此，表示每个是非此即彼的输出看起来像 [["ab"],["ac"],["bc"]] .但是，如果您有 4 个组件，则可以一次创建多个产品。

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

可能带有这些组件的目录产品应类似于 [["ad", "cb"], ["ac", "bd"], ["ab", "cd"]] .
我需要一些有关输出上述数组的函数的逻辑方面的帮助。
下面是一个函数示例，该函数使用提供的组件输出可能的目录产品。但它没有达到上述要求。

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

let catalog = [["a", "b"], ["a", "c"], ["b", "c"], ["c", "d"]];

// Check if subset is included in superset (respecting duplicates).
const isSubset = (subset, superset) => {
  const subsetCount = _.countBy(subset)
  const supersetCount = _.countBy(superset)

  return _.every(subsetCount, (count, value) => supersetCount[value] >= count)
}

catalog.forEach(el => {
if (isSubset(catalog, components) ==  true) console.log(el)
});

// Filter all catalog items, that could be build by components
const matches = _.pickBy(catalog, (catalog, thing) => isSubset(catalog, components))

console.log(matches);

<script src="https://cdn.jsdelivr.net/npm/lodash@4.17.10/lodash.min.js"></script>

编辑:结果应该是一系列可能的目录产品，其组件不与各自阵列中的其他目录产品重叠/冲突。例如，如果我们有...

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

let catalog = ["ab", "ac", "ad", "ae", "bc", "bd", "be", "cd", "ce", "de"];

...输出应该是这样的:

// [ ["ab", "cd"], ["ab", "de"], ["ac", "bd"], ["ac", "be"], ["ad", "ce"], ["ad, "bc"], ["ae", "bc"], ["ae", "cd"] ]

我可能在那里遗漏了一些，但重点是输出应该是一个数组，表达其内部数组的非此即彼关系。产品的组合顺序无关紧要。例如， "cd" == "dc" .内部数组中的任何元素都不应共享组件。例如，我们不应该有 ["ab", "ac"] .

Answer 1

下面的代码是否满足您的要求？

尽可能多地混洗组件数组；

使用数组的拼接功能拼接长度为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;
}