The algorithm for finding circular mappings of the maximum size

Question

I have nine sets of 500 objects each. Although the sets are independent, I assume that the sets share the core of common objects. However, the same object may have a different name (index) depending on the set. But I can measure the pairwise distance between two objects.

Based on pair distances, I have already calculated the optimal mappings between the objects of two sets for all pairs of sets. So, for each pair of sets, I can say the correspondence between any two objects.

Now I want to detect closed display circles, for example. {5 (set 1) → 13 (set 2) → 24 (set 3) → 5 (set 1)}, i.e. Object 5 of set 1 maps to object 13 of set 2, which maps to 24 in set 3, which then goes back to object 5 of set 1. I need this form of circular mapping to state that the objects are essentially the same.

Of course, in an ideal world, I could define most circles covering all nine sets. However, shared objects between 3-9 sets are also interesting. So I need an exhaustive list.

Do you know an algorithm for performing this task or what this problem is called in combinatorial mathematics !?

As a heuristic approach, I would start by defining circles in all combinations of 3 sets, and then combine these results for large combinations of sets.

Answer 1

If I follow your description correctly, you seem to like finding matches between 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 inserts the item into card H. Items with the same key are stored in a linked list. You can find the longest chain by finding the key with the highest frequency in U. Then, by executing H.get (key), you will return the list. Linking the last element to the first, you get the cycle you need.

Hope this helps.