2

给定集合

{1,2,3,4} {2,3,4} {1,4} {1}

什么是查找组的简单（最好是高性能）算法：{1} {2,3} {4}

因为这是最短的集合列表，其中：

  • 所有成员 (1-4) 都有代表。
  • 2 和 3 被组合在一起，因为它们总是一起出现在原始集合中。

真正的数据是一堆引用，而不是值类型。

编辑：我不认为总结我尝试过的内容对解决这个问题有任何帮助，并且只会分散注意力，因为类别理论中可能有一个算法可以解决这个问题，但是（出于娱乐原因）这里是：

  • 我已经汇总了尝试使用联合运算符的哈希集。
  • 我在 gethashcode 上对聚合执行了 groupedby。
  • 我使用第一个条目作为候选集对列表进行了迭代，试图在与其他成员进行比较时逐渐减少它。这表现不佳，我不确定它以尽可能少的套数结束。
4

3 回答 3

7

首先，让我们仔细描述您的问题。

关系是一个函数，它接受两个参数并返回一个布尔值，指示关系是否成立。例如，“小于”是一个关系。

等价关系是一种自反关系——每个项目都与自身相关——对称——如果 A 与 B 相关，则 B 与 A 相关——以及传递——如果 A 与 B 相关且 B 相关与 C 相关，则 A 与 C 相关。

等价关系形成一个集合的等价划分；也就是说，许多子集，其中每个子集中的每个元素都相互关联。每个子集称为一个等价类。例如，整数“A和B是相关的，如果它们的差能被3整除”的等价关系形成三个等价类： 

{0, 3, -3, 6, -6, ... }
{1, 4, -2, 7, -5, ... }
{2, 5, -1, 8, -4, ... }

您希望形成所有集合的并集：

{1, 2, 3, 4} U {2, 3, 4} U {1, 4} U {1} --> {1, 2, 3, 4}

然后将该集合划分为等价类，其中等价关系是“当且仅当 A 和 B 在每个原始集合中总是一起出现时，A 和 B 是相关的”。

首先形成一个字典，将每个元素映射到其相关的等价类。正如您正确指出的那样，最坏的情况是我们有等价划分，其中每个等价类只包含一个元素，所以让我们从它开始。（顺便说一下，这是“A 等于 B”等价关系的等价划分。）

1 --> { 1 }
2 --> { 2 }
3 --> { 3 }
4 --> { 4 }

现在从联合中生成所有无序对的集合：

{ {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4} }

现在对于这些无序对中的每一个，问一个问题“这对关系是否成立”？

对于{1, 2}, {1, 3}, {1, 4}, 关系不成立。

因为{2, 3}关系确实成立，所以将2和3桶合并在一起：

1 -->     { 1 }
2 --\ 
     -->  { 2, 3 }
3 --/
4 -->     { 4 }

因为{2, 4}和{3, 4}关系不成立。

现在你已经完成了，你有一个从每个元素到其对应的等价类的映射。

说得通？

一旦你把它弄对了，有很多方法可以优化这个算法。先把它弄对。

请注意我在这里所做的：我通过解决等价分区的一般问题解决了您的具体问题。如果您对如何编写此程序很聪明，您将能够重用逻辑来解决任何等价分区问题，而不仅仅是您的特定问题。

于 2013-05-31T15:48:17.870 回答
1

这是一种与您得到相同答案的方法：

var sets = new [] { new [] {1,2,3,4}, new [] {2,3,4}, new [] {1,4}, new [] {1}};
var results = sets.SelectMany((x,i) => x.Select(y => new { y, i }))
                .GroupBy(x => x.y).Select(x => new { x.Key, g = string.Join("", x.Select(y => y.i).ToArray())})
                .GroupBy(x => x.g).Select(x => x.Select(y => y.Key).ToArray()).ToArray();

我可能会将此查询的结果定义为可用于组成原始集合的最小集合的最短列表。它使用值的索引作为对它们进行分组的一种方式。（1 出现在 0,2,3 中；4 出现在 0,1,2 等中） 2 和 3 具有相同的索引数组，因此它们在最终结果中组合在一起。

我的第一种方法不适用于集合 {1,2,3,4}、{2,3,4}、{1,4}（答案应该是 {1}、{4}、{2,3} ）。这个会的。

于 2013-05-31T14:53:49.280 回答
0

尽管 Eric Lippert 正确地描述了解决方案，但我没有看到如何为它创建好的并行代码。因此，我不得不使用这种方法。我的解决方案如下

{1,2,3,4} {2,3,4} {1,4} {1}

我们将这些列表的引用分别称为 A、B、C 和 D。

A :{1,2,3,4}
B: {2,3,4}
C: {1,4}
D: {1}

我执行了 SelectMany，将每个成员与它来自的列表的引用相关联。

A, 1
A, 2
A, 3
A, 4
B, 2
B, 3
B, 4
C, 1
C, 4
D, 1

然后我按成员对它们进行分组。

1 : {A,C,D}
2 : {A,B}
3 : {A,B}
4 : {A,B,C}

（在这里我们看到 2 和 3 具有相似的列表，这是可以预期的，因为它们出现在相同的原始列表中）。这也是重点。

为了找到具有相同成员的列表，我通过对列表项对 GetHashcode() 的结果进行异或运算来执行 Aggregate()。所以对于“1”，我有效地做到了

var SomeInt = A.GetHashcode()^C.GetHashcode()^D.GetHashcode().

从而为每个成员生成一个 int 。

1: SomeIntA
2: SomeIntB
3: SomeIntB
4: SomeIntC.

通过对此进行分组。我终于得到了想要的。{1}、{2,3}、{4}

于 2013-06-04T20:47:00.827 回答