<s>[INST] How to find the nth pair from a generated list of pairs? I have a mathematical question applied on informatic (python). I would like to find the fastest way to get the pair from a given index.
As example, we have all pair combinations of values from 0 to 10:
impor itertools
combinations = list(itertools.combinations((i for i in range(0,10)),2)

like this the variable combinations is equals to
[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (4, 5), (4, 6), (4, 7), (4, 8), (4, 9), (5, 6), (5, 7), (5, 8), (5, 9), (6, 7), (6, 8), (6, 9), (7, 8), (7, 9), (8, 9)]

Thus, I have this function to get the nth pair
def row_col_from_index(index: int, no_discrete_values: int):
    row_num = 0
    col_num = 0
    seq_value = 0
    level = 1
    no_columns = 10
    while seq_value <= index + 1 - no_columns:
        no_columns -= 1
        seq_value += (no_discrete_values - level)
        level += 1
    row_num = level - 1
    col_num = level + (index - seq_value)
    return row_num, col_num

Here we get the 24nth pair (indeed array is 0 based)
row_col_from_index(23,10)
-> (2, 9)
combinations[23]
-> (2, 9)

This work but that will be slow to find the corresponding pair with a huge number of values.
So is there a mathematical trick to speedup the computation like a dichotomy approach or other…
And the reverse question for a given pair how to get its corresponding index ?
thanks
 [/INST] Let $n$ play the role of the number $10$: the pairs are: $(0,1),(0,2),\ldots,(0,n-1),(1,2),(1,3),\ldots,(1,n-1),\ldots,(n-2, n-1)$ (all $n\choose 2$ of them).
Let's find a (zero-based) $k$th pair: say it is $(x,y)$. We have $n-1$ pairs starting with $0$, $n-2$ pairs starting with $1$, etc., ending with one pair starting with $n-2$. Thus, the number of pairs starting with something smaller than $x$ is $(n-1)+(n-2)+\ldots+(n-x)=xn-\frac{x(x+1)}{2}$. Obviously, this is $\le k$. Therefore, we have an inequality:
$$xn-\frac{x(x+1)}{2}\le k$$
and we are looking at the largest such $x$. The inequality above is quadratic:
$$x^2+(1-2n)x+2k\ge 0$$
and the solutions are $x_{1,2}=\frac{2n-1\pm\sqrt{4n^2-4n+1-8k}}{2}$. In addition, we are looking for the solutions that are smaller than the "smaller" of the two solutions, as the "larger" one is obviously greater than $\frac{2n-1}{2}$, which is outside the range of $x$ that we are after.
Thus, $x=\left\lfloor \frac{2n-1\pm\sqrt{4n^2-4n+1-8k}}{2}\right\rfloor$. From there, we find the number of pairs preceding the pair $(x, x+1)$ as $xn-\frac{x(x+1)}{2}$ and so $y$ can be found as: $y=k-\left(xn-\frac{x(x+1)}{2}\right)+x+1$.
Something like:
def pair(n, k):
    x = math.floor((2*n-1-math.sqrt(4*n*n-4*n+1-8*k))/2)
    y = k - x*n + x*(x+1)//2 + x + 1
    return x, y

For the inverse, notice that $k=y-(x+1) + xn-\frac{x(x+1)}{2}$.
</s>