题解 | #全排列#

1. 递归

先排序，flag标记数组（是否已排列），index已排列长度

若未排完，遍历标记数组，找到字符并插入，改变标记

递归调用，调用完后记得恢复标记

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

const int maxn=8;
bool flag[maxn];
char s[maxn];
void getpermutation(string str,int index){//递归
  if(index==str.size()){//已排完：输出
    for(int i=0;i<str.size();i++){
      printf("%c",s[i]);
    }
    printf("\n");
  }
  else{
    for(int i=0;i<str.size();i++){//找到排在最前面且没被放入的
      if(flag[i])continue;
      flag[i]=true;//标记已放入
      s[index]=str[i];//插入
      getpermutation(str,index+1);//递归调用直至排完
      flag[i]=false;//标记未被放入，排更大的字符
    }
  }
}

int main() {
    string str;
    while(cin>>str){
      sort(str.begin(),str.end());//先按升序排列
      getpermutation(str,0);
      printf("\n");
    }
    return 0;
}

2. 非递归

找到逆序排列前一个字符（位置记为Index）、逆序排列中第一个比其大的元素

交换，逆置逆序部分

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

bool getnext(string &str){//寻找下一个
  int n=str.size();
  int index=n-2;//降序排列的前一个字符位置
  while(index>=0&&str[index]>str[index+1])index--;
  if(index<0)return false;
  for(int i=n-1;i>index;i--){
    if(str[i]>str[index]){
      swap(str[i],str[index]);//找到第一个比该字符大的，并交换
      break;
    }
  }
  reverse(str.begin()+index+1,str.end());//将降序反转为升序
  return true;
}

int main() {
    string str;
    while(cin>>str){
      sort(str.begin(),str.end());
      do{
        cout<<str<<endl;
      }while(getnext(str));
		cout<<endl;
    }
    return 0;
}

3. 系统自带

• prev_permutation(str.begin(),str.end()) 上个排列
• next_permutation(str.begin(),str.end()) 下个排列

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main() {
    string str;
    while(cin>>str){
      sort(str.begin(),str.end());
     
      do{
        cout<<str<<endl;
      }while(next_permutation(str.begin(),str.end()));
        cout<<endl;
    }
    return 0;
}