Iterate over all unique two-element combinations

Question

I need to iterate over all combinations of two elements: in a set [1,2,3,4] I want to iterate over [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]. Is there an existing tool to do so?

// Not what I need, works wrong!
for (Object o1 : set) {
  for (Object o2 : set) {
    if (o1 == o2) continue;
    ...
  }
}

This code would do twice more operations than needed, because each object will be visited in both loops.

It is trivial to write my own method for that, I just don't want to invent the wheel. I'd expect to find this in Guava or Collections API, but didn't find such functionality.

Answer 1

https://code.google.com/p/combinatoricslib/ Simple combinations section illustrates usage of this utility. Combinations with 2 elements will produce what you wanted.

    // Create the initial vector
    ICombinatoricsVector<String> initialVector = Factory.createVector(
      new String[] { "red", "black", "white", "green", "blue" } );

   // Create a simple combination generator to generate 3-combinations of the initial vector
   Generator<String> gen = Factory.createSimpleCombinationGenerator(initialVector, 3);

   // Print all possible combinations
   for (ICombinatoricsVector<String> combination : gen) {
      System.out.println(combination);
   }

Answer 2

Replacing continue by break nearly does what you want: It produces no swapped pairs. It also halves the overhead (which you don't care about).

You only need to swap the names of o1 and o2 to get exactly the pairs you want.

---

As pointed out in a comment, there's no iteration order guarantee for Sets. So to be sure, convert the Set to a List beforehand. For big sets, this is much cheaper than the pairing itself (O(n) vs O(n*n)).

Answer 3

I am not sure what Set are you going to use but if it has a random access, that is if you can explicitly ask for a member in position i, then you can use a double for with the second iterator gradually increasing: e.g.

for(i = 0; i < Set1_size; i++)
 for(j = i; j < Set1_size; i++)
{ o1.get(i).equals(o2); }

This way you are looping through only ~half (actually half + your main diagonal) the previous comparisons.