How to get all pairs of a set efficiently?

问题:

Given an object of a Set, I want to walk through all (unordered) pairs of it.

Example: Set = {1, 2, 3}, Pairs: (1, 2), (1, 3), (2, 3).

When dealing with a Vector<Integer>, one can achieve this with help of the index of each element:

for (int i = 0; i < vector.size(); i++)
  for (int j = i + 1; j < vector.size(); j++)
    // Do something with vector.get(i) and vector.get(j)

But elements in a Set<Integer> have no indices.

The best solution, I found so far, is to convert the Set to a Vector and use the solution above.

Is there a more efficient / direct solution ?

回答1:

List<Integer> list = new ArrayList<Integer>(mySet);
for (int i = 0; i < list .size(); i++)
    for (int j = i + 1; j < list .size(); j++)
        // Do something with vector.get(i) and vector.get(j)

回答2:

In terms of complexity for this algorithm = n (n -1) / 2, thus O(n^2) is the best you can get (sequential).

Although, if your set is real big, a set that only fits in RAM. You can optimize the algorithm by calculating the pair in a block manner similar to what is done in matrix multiplication using tile blocks. This way you could reduce the % of cache miss and therefore increase the overall performance.

Besides that, you can introduce parallelization and divide work among thread/processes since the algorithm appears to be embarrassingly parallel.