How to find pairs of objects in one list in Java in a good way

Question

Init

I have an ArrayList with different objects. I am trying to search in the same paragraphs of the list of objects by the main condition. If I found the correct Im pairs, creating a new object and adding it to the new list. But I want to avoid creating a pair of objects when objectA pairs with objects B and objectB with object A.

I have not found a good way to do this so far.

Ideas i tried

2 for cycles

 for(Object objectA : objectList){ for(Object objectB : objectList){ if(condition){ // create new object // add to list } } } 

Problem: I need to curiously note already matched pairs, otherwise this will lead to the creation of two created objects for the same pair, which I want to avoid. Does this work, but probably not the best solution?

iterators

Like the version with two forloops, I used an iterator and removed an already matched pair of objects from the list. It works, but doesn't it seem good?

Java8 forEach and removeIf

 objectList.stream().forEach(posA -> { objectList.removeIf(posB -> condition); }); 

Problem: when will I create an object of an object of an object ...?

Question

What is the best idea - or is there a better solution that I have not received?

Answer 1

Apparently, you are considering a disordered pair, where the pair (a, b) matches the pair (b, a). You must create a class yourself for this purpose, for example.

 class Pair<T> { final T a, b; public Pair(T a, T b) { this.a = a; this.b = b; } @Override public boolean equals(Object obj) { if(obj==this) return true; if(!(obj instanceof Pair)) return false; Pair<?> p=(Pair<?>)obj; return Objects.equals(this.a, pa) && Objects.equals(this.b, pb) || Objects.equals(this.a, pb) && Objects.equals(this.b, pa); } @Override public int hashCode() { return Objects.hashCode(a) + Objects.hashCode(b); } } 

Having a class with the required semantics, you can just create all the combinations and let the Stream API remove duplicates. This will even work if the original list already has duplicates:

 List<YourNewObjectType> result = objectList.stream() .flatMap(objA -> objectList.stream().map(objB -> new Pair<>(objA,objB))) .distinct() .filter(pair -> condition) .map(pair -> new YourNewObjectType … ) .collect(Collectors.toList()); 

You did not indicate whether the element should be paired with itself. If not, you can filter out these cases:

 List<YourNewObjectType> result = objectList.stream() .flatMap(objA -> objectList.stream() .filter(objB -> !Objects.equals(objA, objB)) .map(objB -> new Pair<>(objA,objB))) .distinct() .filter(pair -> condition) .map(pair -> new YourNewObjectType … ) .collect(Collectors.toList()); 

As a side note, if building your result type is a side effect free and not expensive, and the type has an equality that reflects the two input elements, you can consider their construction instead of Pair instances and use .distinct for them, while preserving the conversion of Pair instances to instances YourNewObjectType .

If there are no duplicates in your original list, you can use this knowledge to create unique pairs based on indexes:

 List<YourNewObjectType> result = IntStream.range(0, objectList.size()) .mapToObj(i -> IntStream.range(i/*+1*/, objectList.size()) .mapToObj(j -> new Pair<>(objectList.get(i),objectList.get(j)))) .flatMap(Function.identity()) .filter(pair -> condition) .map(pair -> new YourNewObjectType … */) .collect(Collectors.toList()); 

If pairing the element with itself is unacceptable, just translate the comment /*+ 1*/ into a real +1 . This code is less readable, but potentially more efficient.

Answer 2

As @AndyTurner said, I believe this is the best way to implement an ArrayList objectList :

  boolean[] removed = new boolean[objectList.size()]; Arrays.fill(removed, false); // unnecessary List<Pair> result = new ArrayList<>(); for (int i = 0; i < objectList.size(); i++) { if (!removed[i]) { Object objectA = objectList.get(i); for (int j = i + 1; j < objectList.size(); j++) { if (!removed[j]) { Object objectB = objectList.get(j); if (condition) { removed[j] = true; result.add(new Pair(objectA, objectB)); break; } } } } } 

Answer 3

If the list can be ordered, another approach could be:

• sort list

Loop:

• iterating using iterators, deleting a scanned object

• run a binary search for an item that connects to the one you just deleted

• delete this element and create your custom object with these two elements

Thus, you can reduce the time complexity of the study from O (N ^ 2) to O (nlogn).

Answer 4

Why is a non-functional approach unacceptable?

 List<Pair<Object, Object>> pairs = new ArrayList<>(); for (int i = 0; i < objectList.size() - 1; i++) { for (int j = i+1; j < objectList.size(); j++) { if (condition) { pairs.add(new Pair<>(objectList.get(i), objectList.get(j))); } } }