枚举生成排列的方法总结
1. 利用递归的方法枚举 1 ~ n 的所有不重数排列
思路大概就是对一个大小为n的容器,定义一个递归方法 。
每次通过 1 ~ 9 的顺序不断进行放置 ,放置条件为这个数字在容器里面没有出现过 。 ( 递归方法 )
直到放满容器为止打印出当前满足的排列 。 (递归边界条件)
实现代码如下:
/*
利用递归的方法,求 1 ~ n 的全排列
*/
#include <iostream>
#include <cstdlib>
using namespace std;
long long Count; // 定义一个计数器,计数排列种数;
void Printf_Permutation(int n, int cur, int *Num) { // 递归函数;
if (cur == n) { // 递归边界;
cout << "Num " << Count + 1 << " -> ";
for ( int i = 1; i <= n; ++i ) {
cout << Num[i];
i == n ? cout << endl : cout << " ";
}
Count++;
}
else {
for ( int i = 1; i <= n; ++i ) { // 循环和递归调用嵌套的运用形式;
int ok = 1;
for ( int j = 1; j <= cur; ++j ) { // 判断要填进去的数字是不是已经填过;
if (i == Num[j]) ok = 0;
}
if (ok) {
Num[cur + 1] = i; // 吧满足条件的数字填进去,然后递归调用;
Printf_Permutation(n, cur + 1, Num);
}
}
}
}
int main( int argc, char const *argv[] ) {
int n;
cin >> n;
int *Num = (int *)malloc(sizeof(int) * ( n + 1 )); // 动态分配一个数组;
Printf_Permutation(n, 0, Num);
cout << "The All Of Permutation is " << Count << endl;
return 0;
}
思考:博主分析这道题目的时候突然脑洞打开,试想想:递归能不能看成是循环层数未知(自动获取)的高级循环体结构。
2. 利用递归的方法枚举 1 ~ n 的所有可重数排列
如果把问题改成:输入数组P,并按字典序输出数组A各元素的所有全排列。
那么问题也很简单
只需要把上面代码的 i == Num[j] 改成 setN[i] == Num[j] , Num[cur + 1] = i 改成 Num[cur + 1] = setN[i] 然后在 输入待排列的数组setN的时候排好序 。
为了可以出现可重的排序,所以能够递归的判断条件也要改成 countN < CountNum[setN[i] // 判断已经填进容器得某个元素个数是否小于它原本有的元素个数。
为了避免出现 1 1 和 1 1 未两种情况的现象发生,所以必须在循环下面加一条判断条件 if ( i == 1 || setN[i] != setN[i - 1]) 即只有不同的数字才能作为不用的排列填充。
实现代码如下:
/*
利用递归的方法,求 1 ~ n 的全排列
*/
#include <iostream>
#include <cstdlib>
using namespace std;
long long Count; // 定义一个计数器,计数排列种数;
void Printf_Permutation(int n, int cur, int *Num) { // 递归函数;
if (cur == n) { // 递归边界;
cout << "Num " << Count + 1 << " -> ";
for ( int i = 1; i <= n; ++i ) {
cout << Num[i];
i == n ? cout << endl : cout << " ";
}
Count++;
}
else {
for ( int i = 1; i <= n; ++i ) { // 循环和递归调用嵌套的运用形式;
int ok = 1;
for ( int j = 1; j <= cur; ++j ) { // 判断要填进去的数字是不是已经填过;
if (i == Num[j]) ok = 0;
}
if (ok) {
Num[cur + 1] = i; // 吧满足条件的数字填进去,然后递归调用;
Printf_Permutation(n, cur + 1, Num);
}
}
}
}
int main( int argc, char const *argv[] ) {
int n;
cin >> n;
int *Num = (int *)malloc(sizeof(int) * ( n + 1 )); // 动态分配一个数组;
Printf_Permutation(n, 0, Num);
cout << "The All Of Permutation is " << Count << endl;
return 0;
}