How to find the nth pair from a generated list of pairs?

Question

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

Answer 1

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}$.

Answer 2

This correctly solves a related problem. @StinkingBishop answered the one asked.

---

If you are looking at the pairs $(i,j)$ for $0 \le i, j \le N$ then you can think of these pairs as the two digit numbers in base $N$ (with the units digit first). So the pair $(i,j)$ will be at position $jN+i$.

For the reverse calculation, the pair at position $p$ will be $( p\%N, (p - p\%N)/N)$.

(Caveat: The methodology here is well known. I may have the details wrong.)

Answer 3

One way to solve this problem is to work backwards. I'll illustrate my method with a small example, the pairs generated by combinations(range(5), 2). We can write them in a triangular table:

$$\begin{array}{|c|c|c|c|} \hline 0,1 & 0,2 & 0,3 & 0,4\\ \hline 1,2 & 1,3 & 1,4\\ \hline 2,3 & 2,4\\ \hline 3,4\\ \hline \end{array}$$

There are 10 pairs in total, which we can calculate by $4\times 5 / 2$. This is the well-known formula for triangular numbers $$T(n) = n(n+1)/2$$ The first few triangular numbers are $1, 3, 6, 10, 15, 21, 28$

The triangular number formula is a quadratic equation, which we can easily invert, so if we're given some $y=T(n)$ we can find $n$: $$n = \frac{\sqrt{8y+1}-1}{2}$$

So to find a pair, we just need to find the largest triangle that's below it in the triangular table. Eg, counting from the bottom of the table $(1, 4)$ has an index of 4, the largest triangular number $<4$ is $3=T(2)$. So $(1, 4)$ is in the row above those rows containing the $T(2)$ triangle, and it must be at the end of its row.

Here's some Python code that does these calculations.

from itertools import combinations
from math import floor, sqrt

def tri(n):
    return n * (n + 1) // 2

def unrank(idx, n):
    i = tri(n - 1) - idx - 1
    y = (floor(sqrt(8 * i + 1)) - 1) // 2
    j = tri(y) + n - 1 - i
    return n - 2 - y, j

# Test
hi = 5
a = combinations(range(hi), 2)
for i, t in enumerate(a):
    u = unrank(i, hi)
    print(i, t, u, t==u)

Output

0 (0, 1) (0, 1) True
1 (0, 2) (0, 2) True
2 (0, 3) (0, 3) True
3 (0, 4) (0, 4) True
4 (1, 2) (1, 2) True
5 (1, 3) (1, 3) True
6 (1, 4) (1, 4) True
7 (2, 3) (2, 3) True
8 (2, 4) (2, 4) True
9 (3, 4) (3, 4) True

Here's an interactive version to play with, running on the SageMathCell server.