找到第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個比較

回答

相關問題