9

メモリ不足にならずに組み合わせを計算する方法が必要です。これが私がこれまでに持っているものです。

public static long combination(long n, long k) // nCk
{
    return (divideFactorials(factorial(n), ((factorial(k) * factorial((n - k))))));
}

public static long factorial(long n)
{
    long result;
    if (n <= 1) return 1;
    result = factorial(n - 1) * n;
    return result;
}

public static long divideFactorials(long numerator, long denominator)
{
    return factorial(Math.Abs((numerator - denominator)));
}

私は C# としてタグ付けしましたが、ソリューションは理想的には言語に依存しない必要があります。

4

5 に答える 5

22

私が提案した二項係数を計算する最良の方法の 1 つは、Mark Dominusによるものです。N と K の値が大きい場合、他の方法よりもオーバーフローする可能性がはるかに低くなります。

public static long GetBinCoeff(long N, long K)
{
   // This function gets the total number of unique combinations based upon N and K.
   // N is the total number of items.
   // K is the size of the group.
   // Total number of unique combinations = N! / ( K! (N - K)! ).
   // This function is less efficient, but is more likely to not overflow when N and K are large.
   // Taken from:  http://blog.plover.com/math/choose.html
   //
   long r = 1;
   long d;
   if (K > N) return 0;
   for (d = 1; d <= K; d++)
   {
      r *= N--;
      r /= d;
   }
   return r;
}
于 2012-10-20T20:00:48.847 に答える
7 
public static long combination(long n, long k)
    {
        double sum=0;
        for(long i=0;i<k;i++)
        {
            sum+=Math.log10(n-i);
            sum-=Math.log10(i+1);
        }
        return (long)Math.pow(10, sum);
    }
于 2012-10-19T23:44:20.097 に答える
3

コードを見ると、すぐにメモリ不足になってしまうのも不思議ではありません。メソッドは factorialメソッドdivideFactorialsを呼び出し、引数として「分子 - 分母」の差を使用します。コードによると、その差は非常に大きくなる可能性が非常に高く、階乗法で非常に長いループに陥ります。

それが本当にnCkを見つけることだけである場合（コード内のコメントのためだと思います）、次を使用してください：

public static long GetnCk(long n, long k)
{
    long bufferNum = 1;
    long bufferDenom = 1;

    for(long i = n; i > Math.Abs(n-k); i--)
    {
        bufferNum *= i;
    }

    for(long i = k; i => 1; i--)
    {
        bufferDenom *= i;
    }

    return (long)(bufferNom/bufferDenom);
}

もちろん、この方法を使用すると、 long は実際には非常に長い数値をサポートしていないため、範囲を非常に速く使い果たします。そのため、n と k は 20 よりも小さくする必要があります。

実際に非常に大きな数を扱うと仮定すると、累乗がますます重要になるため、long の代わりに double を使用できます。

編集： 大きな数を使用する場合は、スターリングの式も使用できます：

n が大きくなると ln(n!) -> n*ln(n) - n.

これをコードに入れる：

public static double GetnCk(long n, long k)
{
    double buffern = n*Math.Log(n) - n;
    double bufferk = k*Math.Log(k) - k;
    double bufferkn = Math.Abs(n-k)*Math.Log(Math.Abs(n-k)) - Math.Abs(n-k);

    return Math.Exp(buffern)/(Math.Exp(bufferk)*Math.Exp(bufferkn));
}

あなたが言語に依存しないと言ったように、私はこの答えを提案するだけです。C＃コードはそれを実証するために使用されています。これを機能させるには n と k に大きな数を使用する必要があるため、大きな組み合わせの二項係数を見つけるための一般的な方法としてこれを提案します。

n と k の両方が 200 ～ 300 よりも小さい場合は、正確であるため、Victor Mukherjee が提案した答えを使用する必要があります。

Edit2: 最初のコードを編集しました。

于 2012-10-19T23:49:52.427 に答える