4

我有九组，每组 500 个对象。尽管这些集合是独立的，但我假设这些集合共享一个共同对象的核心。但是，一个相同的对象可能具有不同的名称（索引），具体取决于集合。但我可以测量两个物体之间的成对距离。

基于成对距离，我已经计算了所有成对集合的两个集合对象之间的最佳映射。所以，对于每一对集合，我可以说任意两个对象之间的对应关系。

现在我想检测封闭的映射圈，例如{5（set 1）-> 13（set 2）-> 24（set 3）-> 5（set 1）}，即set 1的object 5映射到object 13集合 2，映射到集合 3 中的 24，然后映射回集合 1 的对象 5。我需要这种形式的循环映射来证明对象本质上是相同的。

当然，在理想的世界中，我可以识别出跨越所有九组的大多数圆圈。但是，3-9 组之间的常见对象也很有趣。因此，我想要一份详尽的清单。

你知道执行这个任务的算法，或者这个问题在组合数学中是如何定义的！？

作为一种启发式方法，我将首先确定 3 个集合的所有组合中的圆圈，然后将这些结果组合成更大的集合组合。

4

1 回答 1

0

If I follow your description correctly, it seems you'll like to find correspondences between the sets. Will this algorithm work for you.

 1. Intialize a hashmap H
 2. Initialize key frequency map U = {}
 3. for each set i 
 4.    for each element e in set i
 5.        H.insert {e.key, {i, ...}}
 6.        if U.contain(e.key)
 7.            c = U.get(e.key)
 8.           U.update(e.key,  c + 1)
 9.        else
10.            U.insert(e.key,  1)
11.        endif 
12.    endfor
13. endfor

Line 5 will insert an element into the map H. Elements with the same key are stored in a linked list. You can find the longest chain by finding the the key with the largest frequency in U. Then by doing H.get(key), you'll get back the list. By linking the last element to the first, you'll obtain the cycle you seek.

I hope this helps.

于 2013-02-13T20:45:35.340 回答