Calculation offset when generating all possible pairs in parallel Given a list of n items, I want to generate all possible pairs in parallel through w workers. In other words, each worker must generate only a portion of all possible pairs.
Given n items, there are n(n-1)/2 possible pairs and thus the number of workers w must be 1 <= w <= n(n-1)/2.
Each worker will be given the following parameters:
i: worker number i.e 1,2,3...
w: total workers representing how many workers are used in total.
n: the number of elements in the inintial list.

For instance, if n = 5, there are 10 possible pairs that can be generated.
In case of using 2 workers:
(1,2)⎤
(1,3)
(1,4) worker(1,2,5)
(1,5)
(2,3)⎦

(2,4)⎤
(2,5)
(3,4) worker(2,2,5)
(3,5)
(4,5)⎦

In case of 3 workers:
(1,2)⎤
(1,3)
(1,4) worker(1,3,5)
(1,5)⎦

(2,3)⎤
(2,4) worker(2,3,5)
(2,5)⎦

(3,4)⎤
(3,5) worker(3,3,5)
(4,5)⎦

In order for each worker to generate pairs it must know from which offset (r,c) it should start from. Currently, each worker finds the offset (r,c) it should start from by counting how many pairs were made by the other workers before it.
My intuition tells me there is a formula to find the offset (r,c) which represents the first pair to generate for each worker; however, I wasn't able to come up with it.
 A: The index number of a particular combination (or permutation) in an ordered sequence of combinations is called its rank. The operation of determining a combination from its rank is called unranking.
As you mention, there are 
$$t(n)=n(n-1)/2$$
possible pairs of $n$ items. The numbers $t(n)$ are known as the triangular numbers, and they have been studied since ancient times.
There are various ways to arrange pairs into a triangle. For example:




row
tri









1
0
(0, 1)






2
1
(0, 2)
(1, 2)





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




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



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




The triangular number in the tri column equals the total number of pairs in the previous rows of the table, which means that it's the rank of the pair in the first column of that row. Eg, $6$ is the rank of $(0,4)$. So the key to unranking pairs is to invert the $t(n)$ function.
$$\begin{align}
i &= n(n-1)/2\\
2i &= n^2 - n\\
8i + 1 &= 4n^2 - 4n + 1 = (2n-1)^2\\
n &= \frac{1+\sqrt{8i+1}}{2}
\end{align}$$
If $i$ is a triangular number, $n$ is an integer, and $i$ is the rank of $(0,n)$. If $n$ isn't an integer, $r = \lfloor n \rfloor$, the largest integer $\le n$, gives us the row number of the pair with rank $i$, and $c = i - t(r)$ gives the column number. That is, $i$ is the rank of the pair $(c, r)$
Here's that algorithm, implemented in Python.
def unrank_pair(idx):
    row = floor(1 + sqrt(8 * idx + 1)) // 2
    t = row * (row - 1) // 2
    return idx - t, row

Here's a live demo, running on the SageMathCell server.

Here's an alternative version, which I posted previously in the comments. It produces the pairs in lexicographic order, (column by column, in the table), which may be desirable in some applications. However, it needs to know the total number of rows.
