Compare every item to every other item in ArrayList

Question

I'm having trouble with what I thought should be a pretty simple problem.

I need to compare every item in an arrayList with every other item in the the list without comparing items to themselves. It's not as simple as calling an equals() comparison, it involves some custom logic that I've omitted from my code below. Also the ArrayList should not be changed in any way.

The problem I seem to be having is that once I get into the second loop, I don't know if I have another object to compare to (since its a variable sized list).

for(int i =0; i< list.size(); i++){ 
    //get first object to compare to
    String a = list.get(i).getA();

    Iterator itr = list.listIterator(i + 1 ); // I don't know if i + 1 is valid
    while(itr.hasNext()){
        // compare A to all remaining items on list
    }
}

I think I probably going about this the wrong way, I'm open to suggestions or tips on how to do this better.

Covert

You say that the ArrayList should not be changed in any way, so the size of the list is not variable : it's constant. And i+1 will thus be a valid index for listIterator(), since i is guaranteed to be < list.size() and listIterator accepts an index up to list.size() inclusive. Your code (once trivial syntax errors are fixed), should thus run as is. – Puduns

Awesome, this question helped me tremendously! – Martie

Over at CR, this might fit the Not As Easy As It Looks category (especially with a non-symmetric compare and general java.util.List<>. Starting with compare every item in [a List L] with every other item in [L] – Betsey

Answer 1

for (int i = 0; i < list.size(); i++) {
  for (int j = i+1; j < list.size(); j++) {
    // compare list.get(i) and list.get(j)
  }
}

Suffocate

This will do more comparisons than required, you will be testing if item1 == item3 and item3 == item1 – Gooding

IMHO you can even strip out the "if" since j is always at least i+1 and thus they are never equal. – Cappadocia

Yeah, just realized that it was doing some unnecessary comparisons, updated the code. – Suffocate

@Gooding no, because the inner loop only takes elements that are "behind" the current index in the outer loop. – Cappadocia

I had it initializing j = 0 at first, then fixed it. – Suffocate

Yeah, this actually works, I'm not sure why I was trying to use an iterator, I thought that was the only way to get a sub list. The solution was simple, I was just over thinking this. Thanks – Covert

Also, i only needs to go up to list.size()-2. The last element will have already been compared to all other elements during the loop. – Underdog

What's about the complexity of this method? O(nLog(n))? – Stovall

@chm: I thought it was size()-1 (for i). That's at least how I learned bubble sort back in the days... – Overman

Hi @KalebBrasee, wondering if same solution can be done using for each in Java 8? – Garrek

Answer 2

What's the problem with using for loop inside, just like outside?

for (int j = i + 1; j < list.size(); ++j) {
    ...
}

In general, since Java 5, I used iterators only once or twice.

Numberless

You should read Effective Java item 46, it explicitly recommends against traditional for loops (whenever possible) – Judaica

@Sean Patrick Floyd, JVM can use intrinsic for that, if need be. I dont say at the moment it does use but the iterator is the easiest thing to be optimized away (via escape analysis) – Guberniya

@Guberniya I'm not talking about effective byte code (and neither is Josh Bloch, in this case), but about readable and non-error-prone source code – Judaica

Answer 3

This code helped me get this behaviour: With a list a,b,c, I should get compared ab, ac and bc, but any other pair would be excess / not needed.

import java.util.*;
import static java.lang.System.out;

// rl = rawList; lr = listReversed
ArrayList<String> rl = new ArrayList<String>();
ArrayList<String> lr = new ArrayList<String>();
rl.add("a");
rl.add("b");
rl.add("c");
rl.add("d");
rl.add("e");
rl.add("f");

lr.addAll(rl);
Collections.reverse(lr);

for (String itemA : rl) {
    lr.remove(lr.size()-1);
        for (String itemZ : lr) {
        System.out.println(itemA + itemZ);
    }
}

The loop goes as like in this picture: Triangular comparison visual example

or as this:

   |   f    e    d    c    b   a
   ------------------------------
a  |  af   ae   ad   ac   ab   ·
b  |  bf   be   bd   bc   ·   
c  |  cf   ce   cd   ·      
d  |  df   de   ·         
e  |  ef   ·            
f  |  ·               

total comparisons is a triangular number (n * n-1)/2

Undergarment

Answer 4

In some cases this is the best way because your code may have change something and j=i+1 won't check that.

for (int i = 0; i < list.size(); i++){  
    for (int j = 0; j < list.size(); j++) {
                if(i == j) {
               //to do code here
                    continue;
                }

}

}

Lowery

One interpretation of compare every item in [a List L] with every other item in [L]. It might be about time to ponder/present a java.util.stream-based approach - pity Stream is obliged to be cloneable and provide a useful equals() just as much as Iterator. – Betsey

Answer 5

The following code will compare each item with other list of items using contains() method.Length of for loop must be bigger size() of bigger list then only it will compare all the values of both list.

List<String> str = new ArrayList<String>();
str.add("first");
str.add("second");
str.add("third");
List<String> str1 = new ArrayList<String>();
str1.add("first");
str1.add("second");
str1.add("third1");
for (int i = 0; i<str1.size(); i++)
{
System.out.println(str.contains(str1.get(i)));
}

Output is true true false

Tendance

Answer 6

You can do it like this.

for (int i = 0; i < arrayList.size(); i++) {
    for (int j = 0; j < arrayList.size(); j++) {
        if (i!=j &&  arrayList.get(i).YourObjectItem().equals(arrayList.get(j).YourObjectItem())) {
            //Your code will be here
        }

    }
}

Shapiro

Answer 7

Old question, but I just wanted to provide a functional version from the Kaleb Brasee's one, (which, BTF is far more faster and heap friendly than this) for functional programming purists.

    IntStream.range(0, list.size())
        .forEach(i -> compare(list.get(i),
                               list.subList(i + 1, list.size())));
...

private void compare(final Element element, final List<Element> list) {

    list.stream()
        //whatever 

}

Footsie

just pass it to a set – Norward

Answer 8

Arraylist<String> list =new Arraylist<>();
list.add("water");
list.add("air");
list.add("earth");
list.add("water");

Set<String> set = new LinkedHashSet<>();
      set.addAll(list);
    System.out.println(set.toString())

Norward