欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

next_permutation() 全排列函数

程序员文章站 2022-06-28 20:05:37
next_permutation() 全排列函数 这个函数是 STL自带 的,用来求出该数组的下一个排列组合 相当之好用,~~懒人专用~~ 适用于不想自己用dfs写全排列的同学(结尾附上dfs代码) 洛谷oj可去 "P1008 三连击" 注意: 1. 使用前数组需要排序(升序) 2. prev_pe ......

next_permutation() 全排列函数

这个函数是stl自带的,用来求出该数组的下一个排列组合
相当之好用,懒人专用
适用于不想自己用dfs写全排列的同学(结尾附上dfs代码)

洛谷oj可去 p1008 三连击

注意:

  1. 使用前数组需要排序(升序)
  2. prev_permutation()是求前一个排列组合
  3. 数组 vector都可以,确定全排列的范围
#include <iostream>
#include <algorithm> //函数所需头文件
using namespace std;
int a[10];
void f(){
    int t1,t2,t3;
    t1=a[1]*100+a[2]*10+a[3]*1;
    t2=a[4]*100+a[5]*10+a[6]*1;
    t3=a[7]*100+a[8]*10+a[9]*1;
    if(t1*2==t2&&t1*3==t3) cout<<t1<<" "<<t2<<" "<<t3<<endl;
}
int main(){
    for(int i=1;i<=9;++i) a[i]=i; //sort
    do{
        f();
    }while(next_permutation(a+1,a+10)); //prev_
    return 0;
}

dfs全排列

#include <bits/stdc++.h>
using namespace std;
int a[10];
bool vis[10]={0}; //记录该数字是否被使用过
int n=9;
void dfs(int idx){
    if(idx>n){ //边界输出
        for(int i=1;i<=n;++i) cout<<a[i];
        cout<<endl;
    }
    for(int i=1;i<=n;++i){
        if(!vis[i]){
            vis[i]=1;
            a[idx]=i;
            dfs(idx+1);
            vis[i]=0; //回溯
        }
    }
}
int main(){
    cin>>n;
    dfs(1);
    return 0;
}