Non-recursively generate combinations of pairs of numbers

Question

Is there a technique to non-recursively generate all pair combinations of numbers in an integer sequence. For example for the sequence 0 ... 4:

(1,0)
(2,0) (2,1)
(3,0) (3,1) (3,2)
(4,0) (4,1) (4,2) (4,3)

To clarify: I would like generate a unique combination(i,j) from an arbitrary "index" k. Here's my motivation. I'm writing a GPU kernel in CUDA where each thread considers all pairs of elements from a list and does a computation on them. But the only information that I have is a thread index. And from this thread index I'd like to generate the pair (i,j)

Answer 1

I am assuming you want the first element of the pair to be greater than the second and you want them in lexicographic order, so in your example $(4,1)$ would be at index $8$. If you have $n$ elements in your list there will be $\frac 12n(n-1)$ possible pairs. As you did in the example, consider the list to be $0,1,2,\ldots n-1$. The number of pairs with first element up to and including $k$ is $\frac 12k(k+1)$, the $k^{th}$ triangular number. Given an index $m$ we compute the first element as the largest triangular number strictly below $m$ plus $1$ as $p=\lfloor\frac 12(-1+\sqrt{8(m-1)+1})\rfloor $ Then we have used up $\frac 12p(p+1)$ of the elements, so the second element is $(m-1)-\frac 12p(p+1)$ That gives you the pair.