# 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
-> (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

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

• Thanks. Now I don't have to work this out and fix my answer. Mar 2, 2021 at 18:37

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.)

• These are ordered combinations, without repeats. Eg, in the OPs example, there are 45 pairs from (0, 1) to (8,9). Mar 2, 2021 at 17:15
• @PM2Ring Yes. I just checked. At least this not yet useful answer does start out by stating the question it answers. I'll leave it up and think about fixing it. Mar 2, 2021 at 17:22
• thanks @EthanBolker and PM2Ring for your help Mar 2, 2021 at 17:38
• @bioinfornatics I've looked a little further and I am pretty sure I can solve this problem for you. Maybe later today, not right now. Perhaps someone else will come along sooner. Mar 2, 2021 at 17:40

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.

• Thanks @pm-2ring it is well explained with a usable code Mar 3, 2021 at 13:00