Find keys that have at least n elements in common with another key, containing list

Question

I have a LinkedHashMap of <String, List<T>>. I am building the Map, so maybe there is a better approach to organizing all the data.

I am trying to get the keys that have a common list, with at least 2 elements in common in each lists.

For example:

Map
----------------------
| Key | Values       |
----------------------
| M1  | [A1, A3]     |
| M2  | [A1, A2, A3] |
| M3  | [A1, A2]     |
| M4  | [A2, A3]     |
----------------------

In the end, I wish to have this list: [ [M2, M3], [M2, M4], [M1, M2] ]

• M2 and M3 contain both A1 and A2
• M2 and M4 contain both A2 and A3
• M1 and M2 contain both A1 and A3

I am stuck trying to figure out how to comparing the values of my first entry with the values of all the others. And so on, until I reach the end of my map (like a double for loop for a list).

My solution right now (but I definitely feel like there could be a better way)

List<String> keyList = new ArrayList<>(myMap.keySet());
for(int i = 0 ; i < keyList.size()-1 ; i++) {
    String keyA = keyList.get(i);
    List<T> valuesA = myMap.get(keyA);

    for(int j = 1 ; j < keyList.size() ; j++) {
        String keyB = keyList.get(j);
        List<T> valuesB = myMap.get(keyB);

        // compare both lists here
    }
}

Is using a Map the way to go?

Performance is not an issue for now. But it would be always be better to get something smoother

Answer 1

As I have noticed, you need List<List<Output>> which corresponds to the structure [ [M2, M3], [M2, M4], [M1, M2] ].

Consider the very same input:

Map<String, List<String>> map = new LinkedHashMap<>();      
map.put("M1", Arrays.asList("A1", "A3"));
map.put("M2", Arrays.asList("A1", "A2", "A3"));
map.put("M3", Arrays.asList("A1", "A2"));
map.put("M4", Arrays.asList("A2", "A3"));
    

Here is the working solution:

List<List<String>> output = new ArrayList<>();   // The output List
Set<String> keys = new HashSet<>();              // Key storage used to avoid comparison                            
                                                 // of the keys twice (M1-M2, M2-M1)

for (Entry<String, List<String>> entryOuter: map.entrySet()) {               // First iteration
    if (keys.add(entryOuter.getKey())) {                                     // Adds a new key
        for (Entry<String, List<String>> entryInner: map.entrySet()) {       // Second iteration 
            if (!keys.contains(entryInner.getKey())) {                       // To compare?
                List<String> common = new ArrayList<>(entryOuter.getValue());
                common.retainAll(new ArrayList<>(entryInner.getValue()));    // The common items
                if (common.size() > 1) {                                     // At least 2 common?
                    output.add(Arrays.asList(
                        entryOuter.getKey(), entryInner.getKey()));          // Add these keys
                }
            }
        }
    }       
}

Calling System.out.println(output); prints the desired result:

[[M1, M2], [M2, M3], [M2, M4]]

Briefly the idea described:

• The goal is to iterate each key with a different one only once - achieve 6 iterations.
• Use the Set<String> keys to store the "checked" keys.
• When a unique combination occurs, find the common values.
• If the number of common values is 2 or more, add the keys to the output List as a pair.
• Voilà, the task is done.

You have tagged java-8 so I suggest you might want to use java-stream which provides no real benefit here. linkedhashmap will not help you to iterate easier using indicies unless you implement a workaround: How get value from LinkedHashMap based on index not on key?