题目描述
把 1~n 这 n 个整数排成一行后随机打乱顺序,输出所有可能的次序。
样例
3
输出:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
算法1
(利用递归求解) $O(n^2)$
利用每个位置2种状态,选和不选
利用used数组标记,如果这个位置的数,在上一个位置没被选过就把这个数字选上去
然后递归考虑下一个地方
关于递归,可以关注我的博客,如何思考,如何套用模板,如果调试都有写
https://blog.csdn.net/m0_51373056
时间复杂度
参考文献
C++ 代码
\#include <iostream>
using namespace std;
int a[10010],n;
bool used[10010];
void dfs(int pos,int n)
{
if(pos==n)//递归到了终点了,输出
{
for(int i=0;i<n;++i)
{
cout<<a[i]<<" ";
}
puts("");//换行
return ;
}
else
{
for(int i=1;i<=n;++i)
{
if(!used[i])//如果这个数字没被选过
{
a[pos]=i;//当前位置选上去
used[i]=true;//这个位置标记为选过
dfs(pos+1,n);//递归下一个位置
used[i]=false;
/*
恢复现场,如果到结尾就要return回来了,考虑下一个生成的数列,那么下一个
生成的数列那么每个选过的数字在下一个生成数列都要复原为没选过
*/
}
}
}
}
int main()
{
cin>>n;
dfs(0,n);
}
算法2
(stl) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
int a[10010];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;++i)
{
a[i]=i+1;
}
do
{
for(int i=0;i<n;++i)
{
cout<<a[i]<<" ";
}
cout<<endl;
}while(next_permutation(a,a+n));
return 0;
}