排列(Amn)与组合(Cmn)算法详解

排列(Amn)与组合(Cmn)算法详解

不区分个体差异和顺序时用Cmn(m小n大)，需要区分个体和顺序时候用Amn。

例1：从10个相同的球里取出5个球，不需要区分先后顺序，也不区分其他个体特征，一把抓过去够5个就行，这就是C510(m=5,n=10)。

例2：有10把凳子，需要安排10个人去坐，问有多少种可能性。这里，就需要体现顺序。那么，坐第一个凳子有10种选择，做第二个凳子的有9种选择，以此类推，坐最后一个凳子的就只剩1种选择，每个选择之间是“和”的关系，即为10x9x8x7x6x5x4x3x2x1=A1010=10!。

下面是排列与组合的一般公式：(!代表阶乘）

 A510 = 10! ÷ 5! = 6 x 7 x  8 x 9 x 10

int A(int m, int n)
{int ret = 1;for (int i = m + 1; i <= n; i++)ret *= i;return ret;
}

C38 = (8 x 7 x 6) / (3 x 2 x 1)

 注意"ret = ret * (n - i + 1) / i;"不能写成"ret *= (n - i + 1) / i;" 因为(n - i + 1) / i可能是小数，会计算错误

int C(int m, int n) {int ret = 1;for (int i = 1; i <= m; i++)ret = ret * (n - i + 1) / i;return ret;
}

我们还可以用递推写法，数组记录，用空间换时间，原理就是杨辉三角形，如下图。

void init_C() {for (int i = 0; i < N; i++) { //N表示预处理最大的下标for (int j = 0; j <= i; j++) {if (j == 0 || j == i)//每一行最右边和最左边的数是1c[i][j] = 1;elsec[i][j] = c[i - 1][j] + c[i - 1][j - 1];}}
}

注意：函数写法前一个数（m）比后一个数（n）要小，递推写法数组c[m][n]的前一个数（m）比后一个数n要大。例如：函数写法C(3， 8)  =  递推写法数组c[8][3]