I am interested in performing pairwise comparisons -calculating the euclidean distance between each pair and find the pairs with the highest distance- efficiently. The pairs to be compared should not include neither comparisons with themselves nor with of repeated pairs (i.e. commutative property holds). I could not find any useful resources/algorithms regarding this (trivial?) case.
Here is a short example of what I looking for:
Say I have 4 elements (each is a tuple of 5 values)
A = (32, 12, 46, 13, 75)
B = (55, 8, 68, 25, 41)
C = (43, 21, 64, 66, 64)
D = (56, 19, 17, 54, 89)
that I to be exhaustively compared (i.e. compute the euclidean distance between each pair) with each other:
A against B: 32 against 55, 12 against 8, 46 against 68, 13 against 25, 75 against 41
A against C: 32 against 43, 12 against 21 etc.
A against D
B against A
B against C
B against D
C against D
which has excluded the pairs A-A, B-B, C-C, D-D, B-A, C-A, C-B, D-A, D-B and D-C.
I see that for n elements, I have $ 2^n $ possible comparisons, from which $n$ are the comparisons with themselves.
If someone can point or provide some further analysis regarding the pairwise comparison I describe (e.g. how many commutative comparisons are there for $n$ elements) that would much appreciated.
Also, and perhaps more importantly, I am interested in finding out which algorithm would be the most efficient.
Best Answer
There are $n^2$ (not $2^n$) ordered pairs. Of these, $n$ are pairs of two identical elements. The remaining $n^2-n$ pairs each come in two different orders, of which you want only one, so you have $\frac{n^2-n}2$ different comparisons. This is $\binom n2$, the binomial coefficient that counts the number of ways of choosing $2$ elements out of $n$.