排列组合。。。

排列组合。。。"/>

排列组合。。。

公式。。。

P(n, r) = n! / (n - r)!
c(n, k) = c(n - 1, k) + c(n - 1, k - 1)
c(n, r) = n! / ((n - r)! * r!)

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

组合数打表

void init()
{for (int i = 0; i <= 10; i++){c[i][0] = 1;}for (int i = 1; i <= 10; i++){for (int j = 1; j <= i; j++){c[i][j] = c[i - 1][j - 1] + c[i - 1][j];cout << i << ' ' << j << ' ' << c[i][j] << endl;}}
} 

不全相异的全排列 。。

例：3个a, 2个b，排成一行，求排列数。。
aaabb, aabab, aabba, abaab, ababa, baaab, baaba, abbaa, babaa, bbaaa
n1个物体相同，n2个物体相同。。。nk个物体相同，共有K个不相同的物体。。。排列数为。。
n = n1 + n2 + … +nk;
ans = n! / (n1! * n2! * … * nk!);
定理：用n - 1条边将n个顶点连起来的图有n^(n-2)个。。。

多重集合。。

设多重集合 S = { n1 * a1, n2 * a2, …, nk * ak }；
n = n1 + n2 + … + nk,
即集合 S 中含有n1个元素a1， n2个元素a2，…，nk个元素ak，ni被称为元素ai的重数，k成为多重集合的类别数

在 S 中任选 r 个元素的排列称为S的r排列；
当r = n时，有公式 P(n; n1*a1, n2 a2, …, nk*ak) = n! / (n1! n2! * …* nk!)；（不全相异的全排列）

在 S 中任选 r 个元素的组合称为S的r组合；
当r<=任意ni时，有公式 C(n; n1*a1, n2*a2, …, nk*ak) = C(k+r-1, r),

圆周排列。。

例：a, b, c, d全排列为24种，其中abcd, dabc, cdab, bcda是同一种圆周排列。。。所以只能得到六种。
Q(N, R) = A(N, R) / R; （表示从N 个元素中取R个元素形成圆周排列）
Q(N, N) = (N - 1)!;

next_permutation(a, a + n)函数。。。

用于求下一个按字母表排列的排列数。。
a 要排列的数组地址， n 为要排列的长度。。

a[3] = {1, 2, 3};
do
{cout << a[0] << " " << a[1] << " " << a[2] << endl;
} while (next_permutation(a, a + 3))/*
输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
*/

next_permutation(a, a + 1)
输出 1 2 3;
string类
next_permutation(line.begin(),line.end()）；

借鉴于 ：
组合数学与应用
装逼是一种修行的博客