全排列:从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列
eg:{1,2,3},则123,132,213,231,312,321为它的全排列
思路:二叉树,深度优先搜索(dfs);
说人话就是:
假如是1-3的全排列 首先 遍历第一个位置 为1,第二个位置为2,第三个位置为3,排满后1 2 3;
再将第三个位置清空1 2 * ;
此时第三个位置不能为4(因为1-3最大为3)所以不填继续清空第二个位置1 * *;
此时第二个位置可以为3,第三个位置可以为2
排后 1 3 2;
代码实现:
#include
using namespace std;
//输出n的全排列
int n;
//数组大小
const int len = 11;
//将排列顺序存入数组a中
int a[len];
//判断数组a中有无此元素 初始化为false 表示a无此元素
bool hashTable[len] = {false} ;
//全排列函数
void test(int index)//index表示位置 默认从第一个位置开始
{
//防御性编程 判断是否越界
if (index == n + 1)
{
for (int i = 1; i <= n; i++)
{
cout << a[i] << ' ';
}
cout << endl;
return;
}
//遍历每个位置的可能出现的数据 i为这个位置上的数
for (int i = 1; i <= n; i++)
{
if (hashTable[i] == false)//判断当前排列中有无此元素
{
a[index] = i; //第index位置为i,存入数组
hashTable[i] = true; //若没有则放入并且hashtable为真
test(index + 1); //往下一个位置插入元素 注意数组下标可能越界
hashTable[i] = false;
//“回溯”<=> 最后一个位置插入后 再从后向前清空该位置的数据并且替换
//比如 123 回溯后变成 1** 此时有for循环再次插入值 变为 132
}
}
}
int main()
{
cin >> n;
//从第一个位置开始插入数据遍历
test(1);
return 0;
}
结果展示:
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)