创建唯一组合的数组 [英] 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".]] .

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

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屋！