组合的分组算法

Question

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

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

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

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

组结果将是：

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

示例

为了方便起见，我们将限制为3个类别，但可以有N个。

类别

动物、眼睛颜色、毛发

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

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

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

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

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

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

1. 猫、蓝色、长
2. 猫、蓝色、短
3. 狗、蓝色、长
4. 狗、蓝色、短
5. 狗、绿色、长
6. 老鼠、红色、短
7. 老鼠、蓝色、短

让我们称这个列表为输入(A)

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

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

第二组：
动物      [狗]
眼睛颜色 [绿色 ]
毛发           [长]

第三组：
动物      [老鼠           ]
眼睛颜色 [红色、蓝色]
毛发           [短        ]

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

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

问题

因此，我正在尝试编写生成这些组的算法。我正在尝试使用LINQ来实现，但我也愿意听取其他建议。 有没有关于如何从(A)到(B)的任何建议？

- Mathieu

---

同一输入可能有多个输出。算法应根据某些标准选择“最佳”输出吗？例如，微不足道的输出将是将每个单独的列表项（忽略重复项）组合成一个组。 - kol

抱歉，我可能没有正确理解您的问题，但是这7个项目不是每个都是独立的7个组吗？ - Abhishek Bansal

@kol 很好的观点。标准应该是尽可能少地输出组。我会更新问题以反映这一点。谢谢。 - Mathieu

可能是从这些集合的组合重新创建集合的重复问题。 - David Eisenstat

Answer 1

1. 将每个输入视为一个单独的组。
   • 例如，Cat，Blue，Long成为[Cat]，[Blue]，[Long]的单独组，每个类别恰好有一个项。
2. 按顺序对列表中的每个组进行操作。将其与列表中的每个其他组配对。如果它们符合适当的条件，则将这些组的对组合成单个组。
   • 合并组的条件是n-1个类别的值集相同，并且有仅一个类别集不匹配。 如果是这种情况，则使用n-1个相似类别创建一个新组，其余类别为交集。
3. 如果找到匹配项，请停止比较组并重新从第一组的第一项开始。 （在此处使用延迟执行会有所帮助，因此您不必在找到匹配项后立即将组配对。）
4. 如果您在整个集合中都没有找到匹配项，则完成了，没有更多组合。

---

现在根据示例说明。 首先，它将第一个和第二个组配对。 前两个类别集相同，第三个不同，因此它们可以合并。 现在你有一个列表：

1. [Cat]，[Blue]，[Long, Short]
2. [Dog]，[Blue]，[Long]
3. [Dog]，[Blue]，[Short]
4. [Dog]，[Green]，[Long]
5. [Rat]，[Red]，[Short]
6. [Rat]，[Blue]，[Short]

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

1. [Cat]，[Blue]，[Long, Short]
2. [Dog]，[Blue]，[Long, Short]
3. [Dog]，[Green]，[Long]
4. [Rat]，[Red]，[Short]
5. [Rat]，[Blue]，[Short]

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

1. [Cat，Dog]，[Blue]，[Long，Short]
2. [Dog]，[Green]，[Long]
3. [Rat]，[Red]，[Short]
4. [Rat]，[Blue]，[Short]

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

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

最后，我们将浏览所有组合，但没有一组符合合并条件，于是我们完成了。

- Servy

---

谢谢你的回答！但我还有一些性能上的担忧。我可能会有很多输入条目，我担心所有的循环和比较可能会成为一个问题。我在考虑使用linq，但我猜linq函数在幕后做的事情基本相同？ - Mathieu

@Tigel 你可以使用LINQ或不使用它来完成这个任务。我建议你尝试实现一下，看看是否真的会有问题。这不仅仅是关于输入的大小。请记住，只要找到匹配项，它就可以停止组合，并且每次找到匹配项时，数据的大小就会缩小。如果分组大多在输入序列中靠近彼此，有很多组实际上会被合并在一起，等等，那么情况就不会太糟糕。你还可以通过利用缓存或其他技术来改进它，同时保持相同的基本方法。 - Servy

嗨@Mathieu，我正在尝试实现相同的算法，但效率似乎非常低。您有什么优化上述算法的技巧吗？ - ocind

嗨@ocind，我很难记得一个月前甚至6年前我做了什么。但是我使用了那个算法处理了大量数据，性能还可以接受。我不知道你在使用什么编程语言，但是我使用了结构体而不是类，因为对于数百万个对象的构造函数调用来说，这样更加高效。 - Mathieu