Better ordering
I suggest using colexicographical order, as in that case you won't have to supply the total number of objects. Order your pairs like this:
0: 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: …
0&1, 0&2, 1&2, 0&3, 1&3, 2&3, 0&4, 1&4, 2&4, 3&4, 0&5, 1&5, 2&5, 3&5, …
You'll ve able to extend this list to infinite length, so you can know the index of any pair without knowing the number of items. This has the benefit that when you add new items to your data structure, you'll only have to append to your arrays, not relocate existing entries. I've adjusted the indices to zero-based, as you tagged your question C++ so I assume you'll be using zero-based indexing. All my answer below assumes this ordering.
You can also visualize the colex ordering like this:
a: 0 1 2 3 4 5 …
b:
1 0
2 1 2 index of
3 3 4 5 a&b
4 6 7 8 9
5 10 11 12 13 14
6 15 16 17 18 19 20
⋮ ⋮ ⋱
Pair to single index
Let us first turn a pair into a single index. The trick is that for every pair, you look at the second position and imagine all the pairs that had a lesser number in that position. So for example for the pair 2&4 you first count all the pairs where the second number is less than 4. This is the number of possible ways to choose two items from a set of 4 (i.e. the numbers 0 through 3), so you could express this as a binomial coefficient 4C2. If you evaluate it, you end up with 4(4−1)/2=6. To that you add the first number, as this is the number of pairs with lower index but with the same number in the second place. For 2&4 this is 2, so the overall index of 2&4 is 4(4−1)/2+2=8.
In general, for a pair a&b the index will be b(b−1)/2+a.
int index_from_pair(int a, int b) {
return b*(b - 1)/2 + a;
}
Single index to pair
One way to turn the single index i back into a pair of numbers would be increasing b until b(b+1)/2 > i, i.e. the situation where the next value of b would result in indices larger than i. Then you can find a as the difference a = i−b(b−1)/2. This approach by incrementing b one at a time involves using a loop.
pair<int, int> pair_from_index(int i) {
int a, b;
for (b = 0; b*(b + 1)/2 <= i; ++b)
/* empty loop body */;
a = i - b*(b - 1)/2;
return make_pair(a, b);
}
You could also interpret b(b−1)/2 = i as a quadratic equation, which you can solve using a square root. The real b you need is the floor of the floating point b you'd get as the positive solution to this quadratic equation. As you might encounter problems due to rounding errors in this approach, you might want to check whether b(b+1)/2 > i. If that is not the case, increment b as you would do in the loop approach. Once you have b, the computation of a remains the same.
pair<int, int> pair_from_index(int i) {
int b = (int)floor((sqrt(8*i + 1) + 1)*0.5);
if (b*(b + 1)/2 <= i) ++b; // handle possible rounding error
int a = i - b*(b - 1)/2;
return make_pair(a, b);
}
Sequential access
Note that you only need to turn indices back to pairs for random access to your list. When iterating over all pairs, a set of nested loops is easier. So instead of
for (int = 0; i < n*(n - 1)/2; ++i) {
pair<int, int> ab = pair_from_index(i);
int a = ab.first, b = ab.second;
// do stuff
}
you'd better write
for (int i = 0, b = 1; b != n; ++b) {
for (int a = 0; a != b; ++a) {
// do stuff
++i;
}
}
