组合的分组算法

本文关键字：算法 组合 | 更新日期: 2023-09-27 18:29:01

假设我有一个项目列表，每个项目都由一个简单的结构定义

struct simpleItem
{
    String Category1;
    String Category2;
    ...
    String CategoryN;
}

每个项目都有一系列属于某些类别的值。在处理列表时，类别的数量N是已知的，并且每个项目具有相同数量的类别，并且每个类别只有一个值，不存在重复的项目。但是，每个列表可以有一个不同的类别集。

我正在寻找一种按类别对这些项目进行分组的方法，如果通过组合每个类别排列将这些组分解为单个项目，我最终会得到原始的组合，没有重复。

分组结果为：

struct grouped
{
    String[] Category1;
    String[] Category2;
    ...
    String[] CategoryN;
}

示例

为了这个例子，我们将限制为3个类别，但可能有N.

分类

动物，眼睛颜色，毛发

"动物"类别的选择：猫、狗、大鼠、马

"眼睛颜色"类别的选择：蓝色、黄色、绿色、红色、橙色

"毛发"类别的选择：长、短、卷曲

如果列表包含这3个类别的所有排列，则最终结果将是

第1组：
动物 nbsp nbsp；[猫、狗、老鼠、马]
眼睛颜色[蓝色、黄色、绿色、红色、橙色]
毛皮 nbsp nbsp nbsp nbsp nbsp；[长、短、卷曲]

如果我有一个子列表，例如：

  1. 猫，蓝色，长
  2. 猫，蓝色，短
  3. 狗，蓝色，长
  4. 小狗，蓝色，短
  5. 狗，绿色长
  6. 大鼠，红色，短
  7. 鼠，蓝色，短

让我们调用这个列表，输入（A）

将这些项目分组后，我们可能会得出以下结论：（可能还有其他可能性）。分组标准将是具有尽可能少的输出组。

第1组：
动物 nbsp nbsp；[猫，狗]
眼睛颜色[蓝色毛皮 nbsp nbsp nbsp nbsp nbsp；[长，短]

第2组：
动物 nbsp nbsp；[狗]
眼睛颜色[绿色]
毛皮 nbsp nbsp nbsp nbsp nbsp；[长]

第3组：
动物 nbsp nbsp [老鼠]
眼睛颜色[红，蓝]
毛皮 nbsp nbsp nbsp nbsp nbsp；[短期

让我们将这些组称为输出（B）

正如我们所看到的，通过组合结果组的每个项，我们将返回到（A）中的7个元素的原始输入列表。

问题

所以，我正在尝试编写一个生成这些组的算法。我正试图通过LINQ来做到这一点，但我也愿意接受其他建议。关于如何从（A）到达（B），有什么建议吗？

组合的分组算法

  1. 接受每个输入并将其视为自己的组。
    • 因此，例如，Cat，Blue，Long变成了[Cat]，[Blue]，[Long]的组，每个类别都有一个项目
  2. 从第一组开始，浏览列表中的每一组。将其与列表中的其他组配对。如果这些组符合适当的标准，则将它们组合为一个组。
    • 合并组的标准是，如果n-1个类别的值集相同，并且恰好一个类别集不匹配。如果是这样的话，创建一个新的组，其中n-1个相似的类别是相同的，其余类别是集合的交集
  3. 如果找到匹配项，请停止比较配对，从第一组中的第一个项目开始。（在这里使用延迟执行可以帮助您，这样您就不会在找到匹配项后就麻烦将组配对。）
  4. 如果你看了整盘都没有找到匹配的，那么你就完了，没有更多的组合了

所以，通过你的例子。首先，它将把第一组和第二组配对。前两个类别集是相同的，第三个不同，所以它们可以合并。您现在有一个列表：

  1. [Cat]，[Blue]，[长，短]
  2. [狗]、[蓝]、[长]
  3. [狗]、[蓝]、[短]
  4. [狗]、[绿]、[长]
  5. [鼠]、[红]、[短]
  6. [鼠]、[蓝]、[短]

接下来我们比较（新的）第一组和第二组。第一类和第三类都不匹配，没有合并。接下来我们比较第一类和第三类，同样的两类不会匹配。第一组不会与其他任何一组比赛。现在我们进入第二组。我们把它和第三个配对。它可以合并，因为前两个类别不同：

  1. [猫]、[蓝]、[长、短]
  2. [狗]，[蓝]，[长，短]
  3. [狗]、[绿]、[长]
  4. [鼠]、[红]、[短]
  5. [鼠]、[蓝]、[短]

现在我们重新开始，将第一组和第二组配对。它们匹配。第一类不同，第二类相同，第三类相同。现在是：

  1. [猫，狗]，[蓝]，[长，短]
  2. [狗]、[绿]、[长]
  3. [鼠]、[红]、[短]
  4. [鼠]、[蓝]、[短]

我们现在将第一个与其他三个进行比较，没有一个能比得上。然后，我们将第二个与其他两个进行比较，没有一个能比得上。最后，第三类和第四类将匹配，因为只有第二类不同：

  1. [猫，狗]，[蓝]，[长，短]
  2. [狗]、[绿]、[长]
  3. [大鼠]、[红、蓝]、[短]

最后，我们将检查所有的组合，没有一个组符合合并条件，我们就完成了。

相关文章：