Calculable labels/addresses for combinations?

Question

Given a set of $n$ items (i.e., $\{X_1, X_2, X_3 ... X_n\}$), for all $\binom{n}{2}$ combinations, is there a function I can use to calculate unique labels in the range of $[1, \frac{n (n-1)}{2}]$, given indexes $i, j \in [1, n]$ and $i \neq j$?

E.g., If $n = 5$, I might have the following diagonal table of combinations:

        5   1
      4   D   2
    3   C   G   3
  2   B   F   I   4
    A   E   H   J

• $A$ would be a real number between 1 and 10 that can be calculated by either $f(1, 2)$ or $f(2, 1)$.
• $D$ would be a real number between 1 and 10 that can be calculated by either $f(1, 5)$ or $f(5, 1)$
• $H$ would be a real number between 1 and 10 that can be calculated by either $f(3, 4)$ or $f(4, 3)$

...and each letter's value would not be repeated for another letter. E.g., if $D = 4$ then none of the other letters can be $4$.

If it helps to have some context, I'm writing some computer code and want to index into an array to store the results of the somewhat computationally-expensive combination procedure. The pairs will be received in random order and some may be repeated (in which case I want to lookup the previously computed value).

Answer 1

If I understand the question correctly, you are simply trying to store a lower-triangular matrix in contiguous storage. I.e., you have a collection of values $A_{i,j}$ where $1 \le i \le j$, and you want to map $(i,j)$ to a one-dimensional array index. If so, just map $(i,j)$ to $i + (j-1)j/2$. If the maximum value of $j$ is $N$, you will need an array of size $\frac{1}{2} N (N+1)$.

Answer 2

The type of question has been asked, in various guises, for the $\binom nk$ combinations of $k$ among $n$ elements, for general values of $k$ instead of just $k=2$. See A positional number system for enumerating fixed-size subsets?, and Determining the position of a binary value with $k$ one bits and $n-k$ zeros in an enumeration of $C_k^n$ bit strings, and Generate all k-weight n-bit numbers in pseudo-random sequence.. In this generality, there is an elegant solution called the combinatorial number system.

For $k=2$ this comes down to locating the pair $(a,b)$ with $0\leq a<b<n$ at position $a+\binom b2<\binom n2$ (if you were indexing from$~1$ instead of from$~0$, make sure to correct for that). Should you need to find to pair mapping to a given index$~i$ find the maximal $b$ with $\binom b2\leq i$ (which can be done about as fast and easily as computing integer square roots) and put $a=i-\binom b2$.

Answer 3

It is easier to sort the pairs you receive, then find the index from a sorted pair. If storage is not an issue take $(a,b)$ with $a \ge b$ to $a^2+b$ This wastes about half your indices but is easy. To go the other way, if $n=a^2+b, a=\lfloor \sqrt n\rfloor, b=n-a^2$ If a factor $2$ matters (it shouldn't-do you know the demand that well?) you can use a pairing function