統計問題 - それ自体に対してリストを比較する

Question

これはあなたのためのCompSciまたは統計人です。 theListに72,786の「もの」が含まれていれば、ループの最後にcompareCountの値がどのようになるのでしょうか教えてください。私はそれが72,786であると思っています^ 2-1しかし、それは古い脳がそのように働いてからずいぶん長いことです。あなたの時間と援助を大いに惜しまない！

List<thing> theList = new List<thing>();//list contains 73,786 "things" 
    private void compare() 
    { 
     int compareCount = 0; 
     for(int i = 0; i < theList.Count-1; i++) 
     { 
      for(int comp = i + 1; comp < theList.Count; comp++) 
      { 
       compare(theList[i], theList[comp]); 
       compareCount++; 
      } 
     } 

    } 

Answer 1

コードのcompareCountの値は(72786^2 - 72786)/2 = 2648864505です。私はそれを実行することでそれを確認しました。今書いているように、内部ループにはcompare(theList[i], theList[comp])というコールを持つ必要はありません（カウントには何ら影響しません）。

(n^2 - n)/2の式を覚えていることは次のとおりです。nのラウンドロビントーナメントで、他のすべてのプレーヤーと正確に一度会うことができます。

マッチプランは、nの行と列（n * n = n^2の組み合わせ）の正方形です。プレイヤーは自分自身と対戦しないので、左上から右下に対角線上で一致するnを減算する必要があります（今はn^2 - nと一致しています）。プレイヤーAとプレイヤーBの対角線上の三角形のペアは、下の三角形のAに対してBとのペアと同じです（そのようなペアのうちの(n^2 - n)/2があります）。 n^2 - nからこの数字を引いて、(n^2 - n)/2の最終結果が得られます。