找到第n个比较

我必须比较M项目，其中单个项目不应与自己比较。在这种情况下，我想设计一个算法来查找nth比较。如果，例如，我比较2项则比较的名单应该是：找到第n个比较

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)

等等。

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

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

来源

2016-10-04 drjrm3

我会查看你的问题作为第i个组合，你会发现第i个元素形成C（n，k）的组合列表，在你的情况下k将是2.有一个答案http：// stackoverflow .com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n另外一篇文章https://msdn.microsoft.com/en-us/library/aa289166.aspx – vincentluth

第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

来源

2016-10-04 23:15:22 user1470500

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++; 
     } 
    } 
}

来源

2016-10-05 00:24:56

如果您有序列1, 2, 2, 3, 3, 3, 4, 4, 4, 4有多少数字小于或等于4？有1+2+3+4其中= 10。公式为1+2+...+n = n*(n+1)/2。现在另一种方式，位置x=10上的数字是多少，从1开始计数位置？ 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.代码依赖于事实，即sqrt是确切的。根据IEEE的说法，它应该是，但事实并非如此，sqrt必须作为一个估计值，而最大值必须在整数范围内进行验证。

来源

2016-10-05 00:25:03

找到第n个比较

回答

相关问题