找出第n个比较

Question

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

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

Answer 2

private static void nth(int m, int n) {
    int counter = 1;
    for (int i = 1; i < m; i++) {
        for (int j = i + 1; j <= m; j++) {
            if (counter == n) {
                System.out.println(i + " " + j);
                return;
            }
            counter++;
        }
    }
}

Answer 3

如果您有序列1, 2, 2, 3, 3, 3, 4, 4, 4, 4，有多少个数字小于或等于4?它们有1+2+3+4个= 10个。1+2+...+n = n*(n+1)/2的公式。换一种方式，从1开始数，位置x=10上的数是多少?x = n*(n+1)/2，这是二次方程和n = (sqrt(1+8*x)-1)/2。当x=10时，它是4。7号位置上的数字是多少?这个公式大概是3.275…结果是我们只需要四舍五入就能得到4。

与原始问题的联系很紧密。如果我们从5中减去序列，我们得到4, 3, 3, 2, 2, 2, 1, 1, 1, 1，如果我们反过来，我们得到1, 1, 1, 1, 2, 2, 2, 3, 3, 4。这是第一个数字。第二个数字可以从公式给出的整数到位置的距离来计算，实际上实现起来比解释容易。代码是c#，应该很容易适应C。

int sqrSum(int n)
{
    return n * (n + 1) / 2;
}
void GetNth(int M, int n)
{
    int total = sqrSum(M - 1);
    int nReversed = total + 1 - n;
    int closestBigger = (int)Math.Ceiling((Math.Sqrt(1 + 8 * nReversed) - 1) / 2);
    int difference = sqrSum(closestBigger) - nReversed;
    int i = M - closestBigger;
    int j = i + 1 + difference;
    textBox2.AppendText("(" + i + ", " + j + "), " + Environment.NewLine);
}

代码依赖于这样一个事实，即sqrt是精确的。根据IEEE，它应该是，但如果不是这样，则必须将根号作为估计值，并且必须在整数范围内验证上限。