I have a number n that my program uses to represent a list of natural numbers of size n:
[0,1,2] // n=3
[0,1,2,3,4,5] // n=6
The lists always begin with 0 and their elements appear in sequential order with no numbers skipped. The last element is always (n-1).
Now, I need to get the unique pairs of elements for these arrays. So I wrote an algorithm that takes n as an input, and returns an array of unique pairs of elements from its counterpart above.
[[0,1],[0,2],[1,2]] // n=3
[[0,1],[0,2],[0,3],[0,4],[0,5],[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5]] // n=6
In this implementation, elements cannot pair with themselves (e.g. [0,0]). The pair [1,2] is considered equivalent to [2,1], so only the former would appear.
However, since the pairs have a consistent ordering and follow a basic pattern, I suspect that there is some numeric formula I can use to calculate their values directly—without programmatically creating a list of them.
What I want is a function f(n,i) that would give me the values in the ith pair in the array of pairs for n, for example:
f(3,2) => [1,2]
f(6,8) => [1,5]
Alternatively, it'd be fine to have two functions: One, g(n,i), that returns the first pair-element and another, h(n,i), that returns the second. Like this:
g(3,2) => 1
h(3,2) => 2
g(6,8) => 1
h(6,8) => 5
Is there a formula that can calculate those numbers?
Note: I am not looking for an algorithm to generate the combinations arrays. I have that already. I want to avoid generating array combinations and simply calculate the combination values directly, numerically.
CodePudding user response：
Something like this:
m = n * (n 1) / 2
i = m - i
t = floor(sqrt(2 * i))
[n - t - 1, n - (t i t * (t 1) / 2)]
The trick is to count backward from the end. Otherwise you're basically looking to find the preceding triangular number of i.
CodePudding user response：
Credit to @shawnt00 for the basic idea of inverting the triangular number; I used x = (sqrt(8*i 1) - 1)//2 as the triangular root, which worked out.
def find(n, i):
m = n * (n - 1) // 2
i = m - i - 1
t = (sqrt(8 * i 1) - 1)//2
return (n - t - 2, n - 1 - (i - t * (t 1) // 2))