计算一组序号的第n个组合

Question

我有一个数字 n，我的程序使用它来表示大小为 n:

的自然数列表

[0,1,2] // n=3
[0,1,2,3,4,5] // n=6

列表始终以 0 开头，并且它们的元素按顺序出现，没有跳过任何数字。最后一个元素总是 (n-1).

现在，我需要为这些数组获取唯一的元素对。所以我写了一个算法，它以 n 作为输入，returns 上面对应的一组独特的元素对。

[[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

在此实现中，元素无法与自身配对（例如 [0,0]）。对 [1,2] 被认为等同于 [2,1]，因此只会出现前者。

但是，由于这些对具有一致的顺序并遵循基本模式，我怀疑我可以使用一些数字公式来直接计算它们的值，而无需以编程方式创建他们的名单。

我想要的是一个函数 f(n,i)，它将为我提供 n 对数组中第 i 对的值，例如：

f(3,2) => [1,2]
f(6,8) => [1,5]

或者，最好有两个函数：一个是 g(n,i)，第一个对元素 returns，另一个是 h(n,i)，returns 第二。像这样：

g(3,2) => 1
h(3,2) => 2
g(6,8) => 1
h(6,8) => 5

是否有可以计算这些数字的公式？

注意：我不是在寻找生成组合数组的算法。我已经有了。我想避免生成数组组合，而只是直接以数字方式计算组合值。

Answer 1

f(n, i):
    m = (n - 1) * n / 2 # error check i <= m
    i = m - i # zero-based index
    t = floor((sqrt(8 * i + 1) - 1) / 2)
    r = i - t * (t + 1) / 2
    [n - t - 2, n - r - 1]

诀窍是从末尾倒数。否则，您基本上是在寻找 i 之前的三角数并相对于它进行计算。

维基百科有许多关于三角根的属性，包括上面用于推导三角根的公式。

Answer 2

感谢@shawnt00 反转三角数的基本思想；我用x = (sqrt(8*i + 1) - 1)//2作为三角根，算了。

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

计算一组序号的第n个组合

Calculating the nth combination of a set of sequential numbers

arrays

graph-theory

combinatorics