由於非常大的因子，無法計算組合數量

我正在嘗試計算某個數組中元素數量組合的數量。我需要確切數量的組合來將它用作GPU中要執行的線程數。由於非常大的因子，無法計算組合數量

但是數據非常大，無法用任何數據類型計算該大數的因子。

有沒有一種方法來計算組合的數量，而無需找到階乘？或者更有效的方式來做到這一點？

它總結了此問題：

int no_of_combinations = combination(500,2); 
public static int factorial(int m) 
{ 
     int x = 1; 

     for (int i = m; i > 0; i--) 
      x = x * i; 

     return x; 
} 
public static int combination(int m, int n) 
{ 
    int x = 0; 
    x = factorial(m)/(factorial(n) * factorial(m - n)); 
    return x; 
}

來源

2015-12-09 Abdul Rehman

你能更具體嗎？哪個配方和什麼「非常大」？順便說一句，有一個專門網站的所有數學相關的問題：[http://math.stackexchange.com/]（http://math.stackexchange.com/）。 – Sinatr

我不確定這是否會有所幫助，但您是否擡頭看斯特林的逼近？這是階乘的近似值。 – Alchemist

如果你甚至不能用已知的數據類型表示數字，你將如何創建相同數量的線程？ – HansP

在這種情況下，我會開始簡化公式。在你的例子中，你正在尋找500選擇2，這是500！/ 498！/ 2 !.這可以很容易地更改爲可以計算的500 * 499/2。

一般來講，如果你有ň選擇k，你只需要從ň計算「部分因子」來MAX（K，NK）然後分鐘分裂（K，NK）！由於結果被鏡像，因此導致了。這使得計算更容易。

同樣在某些情況下，您可以開始用min（k，n-k）來分割！雖然相乘，但會導致餘數等

來源

2015-12-09 15:51:26

其實這也是一個有效的方法，更好地與主要除數一起使用，使用Lagendre的公式：https：//en.wikipedia.org/wiki/Legendre%27s_formula –

@BorisStrandjev：在哪些方面更好？例如，什麼是運行時間？ –

@DouglasZare你可以在我建議的方法中計算大量的數字而不用擔心溢出。單個組合的運行時間會比較慢，因爲您需要使用eratosthenes篩選預計算，但對於多次計算來說，運行速度會更快。 –

使用帕斯卡三角屬性：

C（N，K）= C（N - 1，K）+ C（N - 1，K - 1）和動態編程。沒有包含因子。

帕斯卡三角是：

來源

2015-12-09 15:47:38

你需要寫一個新的功能，讓調用它FactorialMoverN

int FactorialMOverN(int m, int n) 
{ 
    int x = 1; 
     for (int i = m; i > n; i--) 
      x = x * i; 
    return x; 
}

然後改變你的組合功能，以

x = FactorialMOverN(m,n) * factorial(m - n));

這應該有所幫助。如果它沒有幫助，那麼你需要使用不同的變量類型，或重新考慮你的問題。

感謝薩米人，我可以看到上述功能是錯誤的。 500選擇2只需要通過

int MChooseN(int m, int n) 
    { 
     int x = 1; 
      for (int i = m; i > (m-n); i--) 
       x = x * i; 
     return x; 
    }

計算以上將採取500，2並返回500 * 499，先前將採取500,2並返回500 * 499 * 498 ... 5 * 4 * 3這不是你想要的。

無論如何，以上是你可以得到的最好的。

來源

2015-12-09 15:48:34

這不會有助於在例如500選擇498的情況下。添加一個簡單的最小/最大值將解決這個問題。 –

是的，我很困惑，因爲我只看他的代碼，而不是他問的實際問題。 +1給你。 –

把它變成'i = m; j> max（n，m-n）'類型，它對500,2和500,498都是一樣的，它們有相同的結果。 –

您不需要使用階乘。如果k> n/2，則使用C（n，k）= C（n，n-k）。然後使用C（n，0）= 1並且對於k> 0，C（n，k）= C（n，k-1）*（nk + 1）/ k。這使您可以計算與動態規劃方法幾乎一樣多的二項式係數，但它需要線性時間（Theta（min（n-k，k）））和恆定空間而不是二次時間和線性空間。

看到這個過去的問題：How to efficiently calculate a row in pascal's triangle?

public static long combination(int n, int k) 
{ 
    if (n-k < k) 
    return combination(n,n-k); 
    if (k < 0) 
    return 0; 
    long result = 1; 
    for (int i=1; i<=k; i++) 
    { 
    result *= n-i+1; 
    result /=i; 
    } 
    return result; 
}

如果答案次數n超過最大長，這可能溢出。因此，如果您希望答案適合32位整數，並且您有64位長整數，那麼這應該不會溢出。爲避免溢出，請使用BigIntegers而不是long。

來源

2015-12-10 00:28:53

由於非常大的因子，無法計算組合數量

回答

相關問題