全排列函数next_permutaton和prev_permutation

//next_permutation:C++中全排列函数(从小到大输出)
//这是一个求一个排序的下一个排列的函数
//next_permutation(num,num+n)函数是对数组num中的前n个元素进行全排列,同时并改变num数组的值。
//需要强调的是,next_permutation()在使用前需要对欲排列数组按升序排序,
//否则只能找出该序列之后的全排列数
//prev_permutation:C++中全排列函数(从大到小输出)
法一:使用数组直接定义(一般这样写就行了):
#include<bits/stdc++.h>
using namespace std;
int a[3]={1,2,3},n;
int main()
{
cin>>n;
do
{
cout<<a[0]<<a[1]<<a[2]<<endl;
} while (next_permutation(a,a+n)); //参数3指的是要进行排列的长度
return 0;
}
法二:使用vector容器

#include<bits/stdc++.h>
using namespace std;
vectora;
vector::iterator it;
int n;
int main()
{
cin>>n;
for(int i = 1; i <= n; i++)
{
a.push_back(i);
}
do
{
for( it = a.begin(); it != a.end(); it++ )
{
cout<<*it;
}
cout<<endl;
}while( next_permutation(a.begin(), a.end()));

return 0;

}
洛谷p1088火星人:
#include<bits/stdc++.h>
using namespace std;
int n,m,s[100000];
int main()
{
cin>>n>>m;
for(int i = 1; i <= n; i++)
{
cin>>s[i];
}
for( int i=1; i<=m;i++)//开始生成到第m个
{
next_permutation(s+1,s+n+1);//s+1—>s+n+1 !!!!
}

for( int i=1; i<=n;i++)
cout<<s[i]<<" ";//输出
return 0;
}
法二:手写next_permutation
#include<bits/stdc++.h>
using namespace std;
int p[10004];
int book[10004]={0};
int k,s;
int f[10004];
int now[10004]={0};

void pint()
{
for(int i=1;i<=k;i++)
{
cout<<p[i]<<" ";
}cout<<endl;
exit(0);
}
void dfs(int step)
{
if(stepk+1){
s–;
// cout<<s<<endl;
if(s
-1)
{
pint();
}
return ;
}
for(int i=(now[step]?1:f[step]);i<=k;i++)
{
if(book[i]==0)
{
book[i]=1;
p[step]=i;
dfs(step+1);
book[i]=0;
}
}
now[step]=1;
}

int main()
{
cin>>k>>s;
for(int i=1;i<=k;i++)
{
cin>>f[i];
}
if(s==0)
{
for(int i=1;i<=k;i++)
cout<<f[i]<<" ";
cout<<endl;
}
dfs(1);
return 0;
}

上一篇:【刷题】【cf】C. Division by Two and Permutation


下一篇:[AGC030F] Permutation and Minimum