c++实现排列与组合

作者: admin 分类: C++ 发布时间: 2020-11-18 14:05

直接实现排列较为难,可以先实现全排列和组合,在组合的每个结果中调用全排列函数,可以较为直观实现非全排列的实现。

我们先来实现组合:对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);

}

 

PermutationAndCombination.rar

如果觉得我的文章对您有用,请随意赞赏。您的支持将鼓励我继续创作!

发表评论

标签云