C++中的组合数(N选R)
声明:本页面是StackOverFlow热门问题的中英对照翻译,遵循CC BY-SA 4.0协议,如果您需要使用它,必须同样遵循CC BY-SA许可,注明原文地址和作者信息,同时你必须将它归于原作者(不是我):StackOverFlow
原文地址: http://stackoverflow.com/questions/9330915/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Number of combinations (N choose R) in C++
提问by Hams
Here I try to write a program in C++ to find NCR. But I've got a problem in the result. It is not correct. Can you help me find what the mistake is in the program?
这里我尝试用 C++ 编写一个程序来查找 NCR。但我的结果有问题。这是不正确的。你能帮我找出程序中的错误吗?
#include <iostream>
using namespace std;
int fact(int n){
if(n==0) return 1;
if (n>0) return n*fact(n-1);
};
int NCR(int n,int r){
if(n==r) return 1;
if (r==0&&n!=0) return 1;
else return (n*fact(n-1))/fact(n-1)*fact(n-r);
};
int main(){
int n; //cout<<"Enter A Digit for n";
cin>>n;
int r;
//cout<<"Enter A Digit for r";
cin>>r;
int result=NCR(n,r);
cout<<result;
return 0;
}
回答by Ben Voigt
Your formula is totally wrong, it's supposed to be fact(n)/fact(r)/fact(n-r)
, but that is in turn a very inefficient way to compute it.
您的公式完全错误,它应该是fact(n)/fact(r)/fact(n-r)
,但这反过来又是一种非常低效的计算方式。
See Fast computation of multi-category number of combinationsand especially my comments on that question. (Oh, and please reopen that question also so I can answer it properly)
请参阅快速计算多类别组合数,尤其是我对该问题的评论。(哦,也请重新打开那个问题,这样我才能正确回答)
The single-split case is actually very easy to handle:
单裂的情况其实很容易处理:
unsigned nChoosek( unsigned n, unsigned k )
{
if (k > n) return 0;
if (k * 2 > n) k = n-k;
if (k == 0) return 1;
int result = n;
for( int i = 2; i <= k; ++i ) {
result *= (n-i+1);
result /= i;
}
return result;
}
Demo: http://ideone.com/aDJXNO
If the result doesn't fit, you can calculate the sum of logarithms and get the number of combinations inexactly as a double. Or use an arbitrary-precision integer library.
如果结果不合适,您可以计算对数的总和,并以双精度形式获得不精确的组合数。或者使用任意精度的整数库。
I'm putting my solution to the other, closely related question here, because ideone.com has been losing code snippets lately, and the other question is still closed to new answers.
我将我的解决方案放在另一个密切相关的问题上,因为 ideone.com 最近一直在丢失代码片段,而另一个问题仍然没有新的答案。
#include <utility>
#include <vector>
std::vector< std::pair<int, int> > factor_table;
void fill_sieve( int n )
{
factor_table.resize(n+1);
for( int i = 1; i <= n; ++i )
factor_table[i] = std::pair<int, int>(i, 1);
for( int j = 2, j2 = 4; j2 <= n; (j2 += j), (j2 += ++j) ) {
if (factor_table[j].second == 1) {
int i = j;
int ij = j2;
while (ij <= n) {
factor_table[ij] = std::pair<int, int>(j, i);
++i;
ij += j;
}
}
}
}
std::vector<unsigned> powers;
template<int dir>
void factor( int num )
{
while (num != 1) {
powers[factor_table[num].first] += dir;
num = factor_table[num].second;
}
}
template<unsigned N>
void calc_combinations(unsigned (&bin_sizes)[N])
{
using std::swap;
powers.resize(0);
if (N < 2) return;
unsigned& largest = bin_sizes[0];
size_t sum = largest;
for( int bin = 1; bin < N; ++bin ) {
unsigned& this_bin = bin_sizes[bin];
sum += this_bin;
if (this_bin > largest) swap(this_bin, largest);
}
fill_sieve(sum);
powers.resize(sum+1);
for( unsigned i = largest + 1; i <= sum; ++i ) factor<+1>(i);
for( unsigned bin = 1; bin < N; ++bin )
for( unsigned j = 2; j <= bin_sizes[bin]; ++j ) factor<-1>(j);
}
#include <iostream>
#include <cmath>
int main(void)
{
unsigned bin_sizes[] = { 8, 1, 18, 19, 10, 10, 7, 18, 7, 2, 16, 8, 5, 8, 2, 3, 19, 19, 12, 1, 5, 7, 16, 0, 1, 3, 13, 15, 13, 9, 11, 6, 15, 4, 14, 4, 7, 13, 16, 2, 19, 16, 10, 9, 9, 6, 10, 10, 16, 16 };
calc_combinations(bin_sizes);
char* sep = "";
for( unsigned i = 0; i < powers.size(); ++i ) {
if (powers[i]) {
std::cout << sep << i;
sep = " * ";
if (powers[i] > 1)
std::cout << "**" << powers[i];
}
}
std::cout << "\n\n";
}
回答by Steven
The definition of N choose R is to compute the two products and divide one with the other,
N 选择 R 的定义是计算两个乘积并将一个与另一个相除,
(N * N-1 * N-2 * ... * N-R+1) / (1 * 2 * 3 * ... * R)
(N * N-1 * N-2 * ... * N-R+1) / (1 * 2 * 3 * ... * R)
However, the multiplications may become too large really quick and overflow existing data type. The implementation trick is to reorder the multiplication and divisions as,
但是,乘法可能会很快变得太大并溢出现有的数据类型。实现技巧是将乘法和除法重新排序为,
(N)/1 * (N-1)/2 * (N-2)/3 * ... * (N-R+1)/R
(N)/1 * (N-1)/2 * (N-2)/3 * ... * (N-R+1)/R
It's guaranteed that at each step the results is divisible (for n continuous numbers, one of them must be divisible by n, so is the product of these numbers).
保证每一步的结果都是可整除的(对于 n 个连续数,其中一个必须能被 n 整除,这些数的乘积也是如此)。
For example, for N choose 3, at least one of the N, N-1, N-2 will be a multiple of 3, and for N choose 4, at least one of N, N-1, N-2, N-3 will be a multiple of 4.
例如,对于N选择3,N、N-1、N-2中的至少一个将是3的倍数,对于N选择4,N、N-1、N-2、N中的至少一个-3 将是 4 的倍数。
C++ code given below.
下面给出的 C++ 代码。
int NCR(int n, int r)
{
if (r == 0) return 1;
/*
Extra computation saving for large R,
using property:
N choose R = N choose (N-R)
*/
if (r > n / 2) return NCR(n, n - r);
long res = 1;
for (int k = 1; k <= r; ++k)
{
res *= n - k + 1;
res /= k;
}
return res;
}
回答by Kaz
A nice way to implement n-choose-k is to base it not on factorial, but on a "rising product" function which is closely related to the factorial.
实现 n-choose-k 的一个好方法是不基于阶乘,而是基于与阶乘密切相关的“上升乘积”函数。
The rising_product(m, n) multiplies together m * (m + 1) * (m + 2) * ... * n, with rules for handling various corner cases, like n >= m, or n <= 1:
raise_product(m, n) 将 m * (m + 1) * (m + 2) * ... * n 相乘,其中包含处理各种极端情况的规则,例如 n >= m 或 n <= 1:
See herefor an implementation nCk as well as nPk as a intrinsic functions in an interpreted programming language written in C:
请参阅此处以了解 nCk 和 nPk 作为用 C 编写的解释性编程语言中的内在函数的实现:
static val rising_product(val m, val n)
{
val acc;
if (lt(n, one))
return one;
if (ge(m, n))
return one;
if (lt(m, one))
m = one;
acc = m;
m = plus(m, one);
while (le(m, n)) {
acc = mul(acc, m);
m = plus(m, one);
}
return acc;
}
val n_choose_k(val n, val k)
{
val top = rising_product(plus(minus(n, k), one), n);
val bottom = rising_product(one, k);
return trunc(top, bottom);
}
val n_perm_k(val n, val k)
{
return rising_product(plus(minus(n, k), one), n);
}
This code doesn't use operators like +
and <
because it is type generic (the type val
represents a value of any kinds, such as various kinds of numbers including "bignum" integers) and because it is written in C (no overloading), and because it is the basis for a Lisp-like language that doesn't have infix syntax.
这段代码不使用像这样的运算符+
,<
因为它是类型泛型(该类型val
表示任何类型的值,例如各种数字,包括“bignum”整数)并且因为它是用 C 编写的(没有重载),并且因为它是没有中缀语法的类 Lisp 语言的基础。
In spite of that, this n-choose-k implementation has a simple structure that is easy to follow.
尽管如此,这个 n-choose-k 实现具有易于遵循的简单结构。
Legend: le
: less than or equal; ge
: greater than or equal; trunc
: truncating division; plus
: addition, mul
: multiplication, one
: a val
typed constant for the number one.
图例::le
小于或等于;ge
:大于或等于;trunc
:截断除法;plus
: 加法, mul
: 乘法, one
: 数字的val
类型常量。
回答by Pulkit Goyal
Use double
instead of int
.
使用double
代替int
。
UPDATE:
更新:
Your formula is also wrong. You should use fact(n)/fact(r)/fact(n-r)
你的公式也错了。你应该使用fact(n)/fact(r)/fact(n-r)
回答by Korchkidu
the line
线
else return (n*fact(n-1))/fact(n-1)*fact(n-r);
should be
应该
else return (n*fact(n-1))/(fact(r)*fact(n-r));
or even
甚至
else return fact(n)/(fact(r)*fact(n-r));
回答by Korchkidu
this is for reference to not to get time limit exceeded while solving nCr in competitive programming,i am posting this as it will be helpful to u as you already got answer for ur question, Getting the prime factorization of the binomial coefficient is probably the most efficient way to calculate it, especially if multiplication is expensive. This is certainly true of the related problem of calculating factorial (see Click herefor example).
这是为了在竞争性编程中解决 nCr 时不要超过时间限制作为参考,我发布这个是因为它对你有帮助,因为你已经得到了你的问题的答案,获得二项式系数的质因数分解可能是最重要的计算它的有效方法,特别是如果乘法很昂贵。这对于计算阶乘的相关问题当然是正确的(例如,请参见单击此处)。
Here is a simple algorithm based on the Sieve of Eratosthenes that calculates the prime factorization. The idea is basically to go through the primes as you find them using the sieve, but then also to calculate how many of their multiples fall in the ranges [1, k] and [n-k+1,n]. The Sieve is essentially an O(n \log \log n) algorithm, but there is no multiplication done. The actual number of multiplications necessary once the prime factorization is found is at worst O\left(\frac{n \log \log n}{\log n}\right) and there are probably faster ways than that.
这是一个基于 Eratosthenes 筛法的简单算法,用于计算质因数分解。这个想法基本上是在使用筛子找到素数时遍历它们,然后还要计算它们的倍数中有多少落在 [1, k] 和 [n-k+1,n] 范围内。Sieve 本质上是一个 O(n \log \log n) 算法,但没有进行乘法运算。找到质因数分解后所需的实际乘法次数最差为 O\left(\frac{n \log \log n}{\log n}\right) 并且可能有比这更快的方法。
prime_factors = []
n = 20
k = 10
composite = [True] * 2 + [False] * n
for p in xrange(n + 1):
if composite[p]:
continue
q = p
m = 1
total_prime_power = 0
prime_power = [0] * (n + 1)
while True:
prime_power[q] = prime_power[m] + 1
r = q
if q <= k:
total_prime_power -= prime_power[q]
if q > n - k:
total_prime_power += prime_power[q]
m += 1
q += p
if q > n:
break
composite[q] = True
prime_factors.append([p, total_prime_power])
print prime_factors
回答by Elyor
Recursive function is used incorrectly here. fact()
function should be changed into this:
递归函数在这里使用不当。fact()
函数应该改成这样:
int fact(int n){
if(n==0||n==1) //factorial of both 0 and 1 is 1. Base case.
{
return 1;
}else
return (n*fact(n-1));//recursive call.
};
};
Recursive call should be made in else
part.
递归调用应该else
部分进行。
NCR()
function should be changed into this:
NCR()
函数应该改成这样:
int NCR(int n,int r){
if(n==r) {
return 1;
} else if (r==0&&n!=0) {
return 1;
} else if(r==1)
{
return n;
}
else
{
return fact(n)/(fact(r)*fact(n-r));
}
};