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

@ShubhamBhewanewala i'm so sorry. my computer crashed and left on vacation... Values are specific. I have a document where I have the x words in 1 article (words are Mx and articles are Ay). So for a selection of articles Ay, I have Mx. Or the other way around, I have Mx words that I'm searching in Ay articles (hope that makes sense) — kanadianDri3, Aug 18 '18 at 20:02

Nikolas Charalambidis · Answer 1 · 2020-09-25T21:26:43.220

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?

score 0 · Answer 2 · answered Jul 21 '18 at 16:01

0

You can use below approach

1) Iterate value of each key in map (that will be a list)

2) Start another iteration from next index of above iteration till end

3) For each element in list of #1, use contains method to check if it is in the list of #2

a) Finish iterating list #3 as soon as two identical objects are found 

b) Iterate list in #3 till last but one if no element one

c) Iterate list in #3 till last if one element found

Hope that will help you

answered Jul 21 '18 at 16:01

Aman Chhabra

3,824
1
23
39

How do you assure to `"start another iteration from next index"` since no Map implementation allows to iterate using index at all? Do you mean: https://stackoverflow.com/q/13581997/3764965? – Nikolas Charalambidis Jul 21 '18 at 17:30

Shubhendu Pramanik · Answer 3 · 2018-07-21T17:44:35.227

Here you go. I've used String instead of Generic:

static Set<String> getCommonKeySet() {
        Map<String, List<String>> map = new HashMap<>();
        Set<String> listOfKeysWithCommonValueSet = new HashSet<>();

        map.forEach((key, value) -> {
            map.entrySet().forEach(entry1 -> {
                List<String> list = new ArrayList<>(value);
                List<String> list1 = new ArrayList<>(entry1.getValue());
                list.retainAll(list1);
                if (list.size() >= 2)
                    listOfKeysWithCommonValueSet.add(key);
            });
        });
        return listOfKeysWithCommonValueSet;
    }

EDIT:

To return Set<Set<String>> use below code:

static Set<Set<String>> getCommonKeySet() {

    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"));
    //Map<String, List<String>> map = new HashMap<>();
    Set<Set<String>> listOfKeysWithCommonValueSet = new HashSet<>();

    map.forEach((key, value) -> {
        map.entrySet().forEach(entry1 -> {
            if(!entry1.getKey().equals(key))
            {
                List<String> list = new ArrayList<>(value);
                List<String> list1 = new ArrayList<>(entry1.getValue());
                list.retainAll(list1);
                if (list.size() >= 2)
                {
                    Set<String> set = new HashSet<>();
                    set.add(key);
                    set.add(entry1.getKey());
                    listOfKeysWithCommonValueSet.add(set);
                }
            }
        });
    });

    System.out.println(listOfKeysWithCommonValueSet);
    return listOfKeysWithCommonValueSet;
}

Output:

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

Even you use the OP's Map as an input the solution produces `[M1, M2, M3, M4]` as output which significantly differs from the OP's expectation `[ [M2, M3], [M2, M4], [M1, M2] ]`. — Nikolas Charalambidis, Jul 21 '18 at 17:25
@Nikolas I just gave a hint, not a full solution. Anyway for that we need to use `Set`. I'll update it. — Shubhendu Pramanik, Jul 21 '18 at 17:33
Still incorrect, produces `[[M1], [M2], [M3], [M4], [M1, M2], [M2, M3], [M2, M4]] `. The inner part should be `if (set.size() > 1) { listOfKeysWithCommonValueSet.add(set); }` — Nikolas Charalambidis, Jul 21 '18 at 17:40
@Nikolas right I need to skip the same keys :). It's not tested code. Thanks... I'll update it. :) — Shubhendu Pramanik, Jul 21 '18 at 17:42

Pankaj Singhal · Answer 4 · 2018-07-22T10:38:48.637

Basic idea is to do the following steps:

1) The original input map.

+------+--------------+
| Keys | Values       |
+------+--------------+
| M1   | [A1, A3]     |
+------+--------------+
| M2   | [A1, A2, A3] |
+------+--------------+
| M3   | [A1, A2]     |
+------+--------------+
| M4   | [A2, A3]     |
+------+--------------+

2) Expanding the mapping in the following manner. Idea is to break the values into subsets so that we can group keys on the basis of values. eg: [A1, A3] present in both M1 & M2 represents [A1, A3] being common in both lists.

+------+--------------+-----------------------------+
| Keys | Values       |                             |
+------+--------------+-----------------------------+
| M1   | [A1, A3]     |                             |
+------+--------------+-----------------------------+
| M2   | [A1, A2, A3] | Expanding this entry        |
+------+--------------+ to create a mapping         +
| M2   | [A1, A2]     | of this key i.e. M2 with    |
+------+--------------+ all the possible            +
| M2   | [A1, A3]     | combinations of the         |
+------+--------------+ original value [A1, A2, A3] +
| M2   | [A2, A3]     |                             |
+------+--------------+-----------------------------+
| M3   | [A1, A2]     |                             |
+------+--------------+-----------------------------+
| M4   | [A2, A3]     |                             |
+------+--------------+-----------------------------+

3) Inverting the above mapping for doing groupBy on the new keys.

+--------------+--------+
| Keys         | Values |
+--------------+--------+
| [A1, A3]     | M1     |
+--------------+--------+
| [A1, A2, A3] | M2     |
+--------------+--------+
| [A1, A2]     | M2     |
+--------------+--------+
| [A1, A3]     | M2     |
+--------------+--------+
| [A2, A3]     | M2     |
+--------------+--------+
| [A1, A2]     | M3     |
+--------------+--------+
| [A2, A3]     | M4     |
+--------------+--------+

4) An inverted map with keys as the common elements & values as their corresponding keys.

+--------------+---------+
| Keys         | Values  |
+--------------+---------+
| [A1, A3]     | [M1,M2] |
+--------------+---------+
| [A1, A2, A3] | [M2]    |
+--------------+---------+
| [A1, A2]     | [M2,M3] |
+--------------+---------+
| [A2, A3]     | [M2,M4] |
+--------------+---------+

Code:

Then the following code creates the above mentioned inverted map in 4th step.

Map<List<Integer>, List<String>> invertedMap = inputMap.entrySet().stream()
    .flatMap(test::getAllCombinationsOfAList)
    .collect(Collectors.groupingBy(Entry::getKey,
        Collectors.mapping(Entry::getValue, Collectors.toList())));

where test::getAllCombinationsOfAList is(with max 2^list_len iterations):

static Stream<Entry<ArrayList<Integer>, String>> getAllCombinationsOfAList(Entry<String,List<Integer>> set)
{
    int n = set.getValue().size();
    Builder<Entry<ArrayList<Integer>,String>> entryStream = Stream.builder();
    for (int i = 0; i < (1<<n); i++)
    {
        ArrayList<Integer> integers = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            if ((i & (1 << j)) > 0)
                integers.add(set.getValue().get(j));
        }

        if(integers.size() >=2 ) {
            entryStream.accept(new AbstractMap.SimpleEntry<>(integers,set.getKey()));
        }

    }
    return entryStream.build();
}

Then the output of res.entrySet().forEach(System.out::println); is:

[1, 2, 3]=[M2]
[2, 3]=[M2, M4]
[1, 2]=[M2, M3]
[1, 3]=[M1, M2]

Here, key_list_length represents the min number of elements which should be common for matching.

value_list_length >=2 represents that there is indeed a matching.

So a key_list_length >= 2 & a value_list_length >= 2 would be the desired output for you. eg:

Map<List<Integer>, List<String>> filteredMap = invertedMap.entrySet()
    .stream()
    .filter(e -> e.getKey().size() >=2 && e.getValue().size() >= 2)
    .collect(Collectors.toMap(Entry::getKey,Entry::getValue));

filteredMap.entrySet().forEach(System.out::println);

Output:

[1, 2]=[M2, M3]
[2, 3]=[M2, M4]
[1, 3]=[M1, M2]

score 0 · Answer 5 · answered Sep 25 '20 at 21:46

Use Map<String, Set<T>> rather than List. Then your own algorithm works like a charm.

Set<T> common = new HashSet<>(valuesA);
common.retainAll(valuesB);
if (common.size() > 1) ...

List would be usable for the map, or even common but is less efficient, less appropriate.

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

5 Answers5