algorithm - 找到第n个比较

Question

我必须比较 M 项，其中不应将单个项与其自身进行比较。在这种情况下，我想设计一个算法来找到第 n 个 比较。例如，如果我正在比较 2 个项目，那么比较列表应该是:

2: (1,2)

同样，如果我比较 3 个项目，比较列表应该是:

3: (1,2), (1,3), (2,3)

遵循这种模式:

4: (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)
5: (1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)

等等。

我的问题是，如果输入是 M，第 nth 项 (i,j) 是什么？

M: (1,2), ..., (i,j), ..., (M-1,M)

虽然我可以很容易地编写一个简单的程序来计算这个临时的，但我想知道是否有一个封闭形式的解决方案，这样它就不会随着 M 扩展。

编辑:为了使这一点更清晰(并有一个可以实现用于测试的示例)，我希望代码位于 C 中，并具有以下模板:

void findIJ(int M, int n) {
    int i = 0;
    int j = 0;

    /* Do work to find i and j*/

    printf("(i,j) = (%i,%i)\n", i, j);
}

Answer 1

第 n 个是 (i, j)，其中:

i = max(k; Sum(M-i, i = 1, k) <= n)
i = max(k; M*k - k*(k+1)/2 <= n)
i = 1 + floor(1/2*(-1+2*M-sqrt(1-4*M+4*M*M-8*(n-1))))

所以:

j = n - M * (i-1) + i*(i+1)/2