Comparing all combinations of elements in a Collection via the Streams API

user_11127623 0
Viewed 119

I'm trying to compare all combinations(i.e. no duplicate comparisons) of elements in a HashMap and returning a List of all the elements of said HashMap which satisfy the comparison function, using the Java 8 Streams-API.
i.e. I want something like this:

// pseudo code, this isnt hashmaps work but hopefully it gets the point across
for(int i=0; i<myHashMap.entrySet().length, i++)
  for(int j=i+1, j<myHashMap.entrySet().length) {
    if(myComparison(entrySet.get(i), entrySet.get(j)))
      myList.add(new myClass[] {entrySet.get(i), entrySet.get(j)})
  }

But using the streams API. I've a version which almost works using .forEach and simply iterating over the stream twice, however this has the issue of running duplicate comparisons and thus adding those duplicates to the list again. I'm fairly certain the reduce operator is capable of what I need but I'm not familiar with Streams API at all and can't figure out how to achieve the desired result.

java-stream data-structures collections functional-programming java
1 Answers

You need to generate all distinct k combinations of the n entries/keys of your map. This post shows how to implement such an algorithm java-combinations-algorithm. But since I think the task is not to come up with such an algorithm, I would suggest to use a librarry which does that task for you. One of such library is combinatoricslib3. If you happen to already use Apache Commons or Guava, they also have implement combinations.

With combinatoricslib3 your code could look like:

import java.util.Map;
import org.paukov.combinatorics3.Generator;

public class TestJavaClass {
    public static void main(String[] args) {
        Map<String,Integer> myMap = Map.of("Foo", 1, "Bar", 2, "Baz", 3);
        Generator.combination(myMap.keySet())
                .simple(2)
                .stream()
                .forEach(System.out::println);
    }
}

Output:

[Foo, Baz]
[Foo, Bar]
[Baz, Bar]

I have used the key set above to show a simple example. But if you need the entries you can change it to:

Generator.combination(myMap.entrySet())...

to get the combination of entries:

[Foo=1, Baz=3]
[Foo=1, Bar=2]
[Baz=3, Bar=2]

Not sure what your myComparison method does, but since you use it as a condition in an if statement, I assume it returns a boolean. If so you can use it as a filter to process the stream further. With a dummy implementation of your method myComparison and your custom class MyClass something like below should give you a starting point:

import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
import org.paukov.combinatorics3.Generator;
import lombok.AllArgsConstructor;

public class TestJavaClass {

    public static void main(String[] args) {
        Map<String, Integer> myMap = Map.of("Foo", 1, "Bar", 2, "Baz", 3);
        List<MyClass> result =
                Generator.combination(myMap.entrySet())
                        .simple(2)
                        .stream()
                        .filter(comb -> myComparison(comb.get(0), comb.get(1)))
                        .map(comb -> new MyClass(comb.get(0), comb.get(1)))
                        .collect(Collectors.toList());
    }

    static boolean myComparison(Map.Entry<String, Integer> first, Map.Entry<String, Integer> second) {
        return first.getValue() + second.getValue() <= 4;
    }

    @AllArgsConstructor
    static class MyClass {

        Map.Entry<String, Integer> one;
        Map.Entry<String, Integer> two;
    }
}
user_51769920
Related