6

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

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

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

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

一组结果将是：

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

例子

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

类别

动物，眼睛颜色，毛皮

“动物”类别的选择：猫、狗、老鼠、马

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

“毛皮”类别的选择：长、短、卷曲

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

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

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

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

我们称这个列表为 Input (A)

在将这些项目分组后，我们最终可以得到：（可能还有其他可能性）。分组标准是尽可能少的输出组。

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

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

第 3 组：
动物 [鼠]
眼睛颜色 [红、蓝]
毛皮 [短]

我们称这些组为输出(B)

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

问题

所以，我正在尝试编写一个生成这些组的算法。我正在尝试使用 LINQ 执行此操作，但我也愿意接受其他建议。关于如何从(A)到达(B)有什么建议吗？

4

1 回答 1

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

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

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

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

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

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

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

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

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

最后，我们将遍历所有组合，没有一个组匹配合并条件，我们就完成了。

于 2013-08-26T15:22:28.913 回答