n番目の比較を見つける

Question

私はMと比較しなければならない項目を1つの項目と比較してはいけません。この場合、nthの比較を見つけるアルゴリズムを設計したいと思います。例えば、私は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合わせて拡張しないようにこれに対する閉形式解がある場合、私は疑問に思って。

EDIT：このより明確なカットを作るために（およびテストのために実装することができる例を持っている）、私は、次のテンプレートとCにするコードを希望：

Answer 1

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

N

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

そしてそう：番目は、と（i、j）はある

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つの方法は、位置の番号は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となります。これが私たちのペアの最初の数です。第2の数は、数式が整数を与える位置までの距離から計算することができ、説明するより実際に実装する方が簡単です。コードは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によればそうであるはずですが、それはそうではありませんでしたが、sqrtは推定値として取られなければならず、天井は整数範囲で検証されなければなりませんでした。