组合的分组算法

Question

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

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

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

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

小组结果将是:

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

例

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

动物,眼睛颜色,毛皮

选择"动物"类别:猫,狗,鼠,马

选择"眼睛颜色"类别:蓝色,黄色,绿色,红色,橙色

"毛皮"类别的选择:长,短,卷曲

如果列表具有这3个类别的所有排列,则最终结果将是

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

如果我有一个子列表,例如:

我们叫这个清单,输入(A)

在将这些项目分组后,我们最终会得到:(可能还有其他可能性).分组标准是尽可能减少输出组.

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

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

第3组:
动物[大鼠]
眼睛颜色[红色,蓝色]
毛皮[短]

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

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

所以,我正在尝试编写一个生成这些组的算法.我试图用LINQ做这个,但我也愿意接受其他建议.关于如何从(A)到达(B)的任何建议？

Answer 1

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

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

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

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

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

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