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 回答