c++实现排列与组合
直接实现排列较为难，可以先实现全排列和组合，在组合的每个结果中调用全排列函数，可以较为直观实现非全排列的实现。
我们先来实现组合：对C(N,M)，如果M已知，则直接写M值已知，则直接写M个嵌套循环即可实现。例如，M=3：
for(int i=0;i<len;i++)
for(int j=i+1;j<len;j++)
for(int k=j+1;k<len;k++){
//do
}
对于M值未知的情况，则可以用递归实现组合。
void Combination(vector<int> &a, vector<int> &b, int l, int m, int M){
//b用于临时存储结果。len(b)==M；l为左侧游标，初始值取0；M是取出个数；m用于指示递归深度，初始值取M）
int N = a.size();
if (m == 0) {
for (auto i : b){
cout << i << ' ';
}
cout << endl;
return;
}
for (int i = l; i < N; i++){
b[M-m] = a[i];
Combination(a, b,i+1,m – 1,M);
}
}
下面实现全排列，全排列可以自己实现，也可以使用stl算法。自己实现全排列算法，也是使用递归，但是比组合要多一步回溯：
void Permutation(vector<int> &a, vector<int> &b, int l){
//b用于临时存储结果。len(b)=len(a),l为左侧游标，初始值取0
int len = a.size();
if (l == len) {
for (auto i : b){
cout << i << ' ';
}
cout << endl;
return;
}
for (int i = l; i < len; i++){
b[l]= a[i];
swap(a[i], a[l]);
Permutation(a, b,l+1);
swap(a[i], a[l]);
}
}
stl的全排列：
void how_to_use_next_permutation(vector<int> &a){
//使用STL 算法实现全排列
auto it1 = a.begin();
auto it2 = a.end();
sort(it1, it2);
do{
for (auto i : a){
cout << i << ' ';
}
cout << endl;
}while (next_permutation(it1, it2));
}
有了组合和全排列算法，我们可以进一步写出排列：
void Arrangement(vector<int> &a, vector<int> &b, int l, int m, int M){
//b用于临时存储结果。len(b)==M；l为左侧游标，初始值取0；M是取出个数；m用于指示递归深度，初始值取M）
int N = a.size();
if (m == 0) {
vector<int> c(M);
//Permutation(b, c,0);
how_to_use_next_permutation(b);
//cout << endl;
return;
}
for (int i = l; i < N; i++){
b[M – m] = a[i];
Arrangement(a, b,i + 1, m – 1,M);
}
}
全部代码如下：
#include <iostream>
#include <stdio.h>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
using namespace std;
void how_to_use_next_permutation(vector<int> &a);
void Permutation(vector<int> &a, vector<int> &b, int l){
//b用于临时存储结果。len(b)=len(a),l为左侧游标，初始值取0
int len = a.size();
if (l == len) {
for (auto i : b){
cout << i << ' ';
}
cout << endl;
return;
}
for (int i = l; i < len; i++){
b[l]= a[i];
swap(a[i], a[l]);
Permutation(a, b,l+1);
swap(a[i], a[l]);
}
}
void Combination(vector<int> &a, vector<int> &b, int l, int m, int M){
//b用于临时存储结果。len(b)==M；l为左侧游标，初始值取0；M是取出个数；m用于指示递归深度，初始值取M）
int N = a.size();
if (m == 0) {
for (auto i : b){
cout << i << ' ';
}
cout << endl;
return;
}
for (int i = l; i < N; i++){
b[M-m] = a[i];
Combination(a, b,i+1,m – 1,M);
}
}
void Arrangement(vector<int> &a, vector<int> &b, int l, int m, int M){
//b用于临时存储结果。len(b)==M；l为左侧游标，初始值取0；M是取出个数；m用于指示递归深度，初始值取M）
int N = a.size();
if (m == 0) {
//vector<int> c(M);
//Permutation(b, c,0);
how_to_use_next_permutation(b);
//cout << endl;
return;
}
for (int i = l; i < N; i++){
b[M – m] = a[i];
Arrangement(a, b,i + 1, m – 1,M);
}
}
void how_to_use_next_permutation(vector<int> &a){
//使用STL 算法实现全排列
auto it1 = a.begin();
auto it2 = a.end();
sort(it1, it2);
do{
for (auto i : a){
cout << i << ' ';
}
cout << endl;
}while (next_permutation(it1, it2));
}
int main(){
int M = 3, N = 4;
vector<int> a,b(M),c(N);
for (int i = 1; i <= N; i++){
a.push_back(i);
}
printf( "1~%d Permutation:\n",N);
Permutation(a, c, 0);
printf("\nM=%d, N=%d Combination:\n",M ,N);
Combination(a, b, 0,M,M);
printf("\nM = %d, N = %d Arrangement:\n",M ,N);
Arrangement(a, b, 0,M,M);
printf("\nhow_to_use_next_permutation:\n");
how_to_use_next_permutation(a);
while (1);
}
