创建一个独特组合的数组 [英] Creating an Array of Unique Combinations

问题描述

我有一个组件数组:

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

可以将这些组件组合起来制造产品；即，a"；+b"=ab".

It is possible to combine those components to make products; i.e., "a" + "b" = "ab".

我有一份可能的产品目录:

I have a catalog of possible products:

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

使用 lodash 之类的东西，我们可以创建一系列可能的产品.输出数组看起来像 [ab"、ac"、bc"].

Using something like lodash, we can create an array of possible products. Output array would look like ["ab", "ac", "bc"].

但问题在于，并非所有这些产品都可以构建，因为一旦使用了一个组件，它就不再可用于其他需要它的产品.

But the problem is that not all of those products could be built because once the component for one is used, it is no longer available for use in other products that require it.

我需要一个只显示可能结果的输出.当只有 3 个组件，并且每个目录产品需要 2 个时，显然不可能一次创建多个产品.因此，表示每个都是非此即彼的输出看起来像 [[ab"],[ac"],[bc"]].但是，如果您有 4 个组件，则可以一次创建多个产品.

I need an output that only shows possible outcomes. When there are only 3 components, and every catalog product requires 2, obviously it's not possible to create more than one product at a time. So an output that would express that each is either-or would look like [["ab"],["ac"],["bc"]]. But if you have 4 components it is possible to create more than one product at a time.

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

包含这些组件的可能目录产品应类似于 [[ad"、cb"]、[ac"、bd"]、[ab"、cd"]]].

Possible catalog products with these components should look like [["ad", "cb"], ["ac", "bd"], ["ab", "cd"]].

我需要一些关于输出上述数组的函数的逻辑方面的帮助.

I need some help with the logic for a function that outputs an array like the above.

下面是一个函数示例，该函数使用提供的组件输出可能的目录产品.但它并没有达到上述要求.

Below is an example of a function that outputs possible catalog products with the provided components. But it doesn't achieve the requirements stated above.

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>

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

The result should be an array of possible catalog products whose components do not overlap/conflict with other catalog products in their respective arrays. So for example, if we have...

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

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

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

... the output should be something like:

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

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

It's possible I've missed some there, but the point is that the output should be an array that expresses the either-or relationship of its inner arrays. The products' combination order doesn't matter. For example, "cd" == "dc". No element in the inner arrays should share a component. For example, we should not have ["ab", "ac"].

推荐答案

已编辑以适应您评论中的需求.此示例使用一个相当简单的递归函数来生成所有唯一组合，并带有限制最大组合大小的选项(用于生成只有大小为 2 的组合的 catalog).

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).

possibleProducts 是通过将 catalog 数组无限制地传递给同一函数而生成的所有唯一组合的过滤数组.

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; }

这篇关于创建一个独特组合的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！