全排列

#通过递归交换数组，得到一个无重复列表的全排列
#需要注意几点，输入字母未排序，输出最后还要加一个空格（应该是利于某些算法）

#这函数输入如果是有序的可以得到按顺序的全排列
def allPermute(array):
    result = []
    tempArray = list(array)
    def exchange(num):
        nonlocal tempArray
        nonlocal result
        if num == len(tempArray)-1:
             result.append(list(tempArray))
        else:
            for j in range(num,len(tempArray)):
                tempArray[num],tempArray[j] = tempArray[j],tempArray[num]
                exchange(num+1)
                tempArray[num], tempArray[j] = tempArray[j], tempArray[num]
    exchange(0)
    return result
try:
    while True:
        string = list(input())
        temp = allPermute(string)
        temp.sort()
        for i in temp:
            print("".join(i))
        print()
except Exception:
    pass

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <stack>
#include <queue>
#include <math.h>
#include <functional>
using namespace std;
bool mark[10];
char Out[10]; 
char In[10];
int len;
void DFS(int num){
    if(num == len){ // 递归退出，0 - len-1位的字符已经就位，输出即可
        Out[num] = '\0';
        puts(Out);
        return;
    }
    for(int i = 0;i < len;i++){
        if(mark[i] == 1) continue; //使用过跳到下一次循环
        mark[i] = 1;
        Out[num] = In[i]; //加到输出字符数组
        DFS(num + 1);
        mark[i] = 0; //回溯
    }
}

int main(){
    while(gets(In)){
        len = strlen(In);
        sort(In,In + len); //给定的并没有排好序
        DFS(0);
        cout<<endl;
    }
    return 0;
}

#include"iostream"
using namespace std;
void fP(string ipt, string flags, string res, int idx){
    if(idx== ipt.length()){cout<< res<< endl;}
    else{
        for(int i= 0; i< flags.length(); i++){
            if(flags[i]== '0'){
                res[idx]= ipt[i];flags[i]= '1';
                fP(ipt, flags, res, idx+ 1);
                flags[i]= '0';
            }
        }
    }
}
int main(){
    string ipt;
    while(cin>> ipt){
        fP(ipt, string(ipt.length(), '0'), string(ipt.length(), ' '), 0);
    }
}

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

const int MAXN = 10;

bool visit[MAXN];     //字符串内某个字母是否被遍历过
char sequence[MAXN];  //结果

//全排列可以用一个树表示，index就表示当前所处在第几层
void GetPermutation(string str,int index){
    if(index == str.size()){
        for(int i=0;i<str.size();i++){
            printf("%c",sequence[i]);
        }
        printf("\n");
    }else{
        for(int i=0;i<str.size();i++){
            if(visit[i] == true){
                continue;
            }
            visit[i]=true;
            sequence[index]=str[i];
            GetPermutation(str,index+1);
            visit[i]=false;
        }

    }
    return;

}
int main()
{
    string str;
    while(cin>>str){
        sort(str.begin(),str.end());  //将字符串按照字典顺序排序
        GetPermutation(str,0);
        printf("\n");
    }
    return 0;
}

#include <iostream>
(720)#include <string>
#include <vector>
using namespace std;
vector<string> v;
void dfs(int* flg,string str,int len){
    if(str.length()==len){
        v.push_back(str);
        return;
    }
    for(int i=0;i<300;i++){
        if(flg[i]==1){
            flg[i]=0;
            dfs(flg,str+char(i),len);
            flg[i]=1;
        }
    }
    return;
}

int flg[300];

int main(){
    string str;
    cin>>str;
    for(int i=0;i<str.length();i++) flg[str[i]]++;
    dfs(flg,"",str.length());
    for(int i=0;i<v.size();i++){
        cout<<v[i]<<endl;
    }
    cout<<endl;
}
/*
题目有点问题：题目说a<b<...<A<B<...<Y<Z。但是实际上ascii码是大写字母排在前面。
按ascii码排序的话，如果sample里有大小写混合的字符串就会报错。
然而并没有。
要么是题目写错，要么是样例设计的不完整。
至于我，懒得改了。
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmp(const void *a,const void *b) {
    return *(char*)a-*(char*)b;
}
int factorial(int n) {
    if(n==0) return 1;
    return n*factorial(n-1);
}
void all_sorts(char **list,int first,int n,int len) {
    if(n>=2) {
        all_sorts(list,first,n-1,len);
        int gap=factorial(n-1);
        for(int i=1; i<n; i++) {
            int site=first+gap*i;
            list[site]=(char*)malloc(sizeof(char)*7);
            int start=len-n;
            for(int j=0; j<start; j++) list[site][j]=list[first][j];
            list[site][start]=list[first][start+i];
            int top=start;
            for(int j=start; j<=len; j++) if(j!=start+i) list[site][++top]=list[first][j];
            all_sorts(list,site,n-1,len);
        }
    }
}
int main() {
    char str[7];
    while(scanf("%s",str)!=EOF) {
        int len=strlen(str);
        char **multilist=(char**)malloc(sizeof(char*)*factorial(len));
        qsort(str,len,sizeof(char),cmp);
        multilist[0]=str;
        all_sorts(multilist,0,len,len);
        for(int i=0; i<factorial(len); i++) printf("%s\n",multilist[i]);
        printf("\n");
    }
    return 0;
}

参考https://blog.csdn.net/beggar200/article/details/50245207


#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

bool next_perm(char *perm,int n){
    int i=n-2;
    while(i>=0&&perm[i]>perm[i+1])
        i--;   //find x
    if(i<0)
        return false;

    int j=n-1;
    while(j>i&&perm[j]<=perm[i])
        j--; //find y;

    swap(perm[i],perm[j]);
    reverse(perm+i+1,perm+n);
    return true;


}
int main(){
    char str[7];
    while(scanf("%s",str)!=EOF){
        int n=strlen(str);
        sort(str,str+n);
        printf("%s\n",str);
        while(next_perm(str,n))
            printf("%s\n",str);
        printf("\n");
        
    }

}

	

#include<iostream>
#include<algorithm>
using namespace std;
void f(string pre, string s){
    if(pre.size()==s.size()){cout<<pre<<endl;return;}
    for(int i=0;i<s.size();i++){
        int ok=1;
        for(int j=0;j<pre.size();j++){
            if(pre[j]==s[i]){ok=0;break;}
        }
        if(ok)f(pre+s[i], s);
    }
}
int main(){
    string s;
    while(cin>>s){
        sort(s.begin(),s.end());
        f("", s);
        cout<<endl;
    }
    return 0;
}

#include<iostream>
#include <vector>
#include <algorithm>
#include<string>
using namespace std;
class Solution {
public:
     vector<string> Permutation(string str) {
          if(str!="") {
              sort(str.begin(),str.end());//保证了字典序输出，因为abc，一次交换是bac,不恢复状态，所以下次交换是cab。
              dfs(str,0);
          }
          return result;
     }
     void Print(){
          for(int i=0;i<result.size();i++){
              cout<<result[i]<<endl;
          }
     }
private:
     void dfs(string str,int s){
          int sz = str.size();
          if(s==str.size()){
              result.push_back(str);
              return;
          }
          for(int i=s;i<sz;++i){
              if(i!=s&&str[i]==str[s]) continue;
              swap(str[i],str[s]);
              dfs(str,s+1);
          }
     }
     vector<string> result;
};
int main(){
    string str;
    cin >> str;

     Solution sol;
     sol.Permutation(str);//不加sort"acb"会不按照字典序输出
     sol.Print();
    return 0;
} 

/**
*八皇后问题，使用递归的方法来解
*怎么说呢，萌新觉得这题递归的写法和玛雅人的密码那题挺像的（我抄别人的代码）
*萌新就是一张白纸，觉得这种递归很神奇，理由如下
*①递归中使用全局数组，大家一起用一个，每次递归结束后都要恢复全局变量为原值
*②递归中使用一个循环这个我也觉得很骚，印象中自己只会那种if return的语句模式的
*根据数列递推公式写的递归函数
*其他类型语句出现在递归函数中，萌新觉得很神奇。
*在玛雅人的密码那题中，是不断的移位，设置移位的标志变量flag[]来记录是否移位，
*如果已经移位了的话就不对节点进行扩展
*本题中，通过设置标志变量数组flag[]来记录当前字符是否被使用过，
*如果使用过了的话就继续寻找，结果是存在一个全局字符数组res中
*我们可以仔细的思考一下res可能的作用域，
*它的作用域范围绝对不可能是在递归函数里面，
*因为如果在递归函数里声明它的话，递归子层也会声明一个这个数组，
*那么无法做到所有的递归函数都使用同一个数组。
*实际上对于老手来说，他们都不会思考这种萌新才想的事情
*因为不同层的递归都要对这个结果数组进行写操作，
*换言之，它必须被所有层的递归函数共享
*除了全局变量，还有谁能做到这一点？？？还有谁？？？
*当然还有另一种放法，在main函数中定义res，
*将它作为参数传给递归函数，递归函数再把res传给它调用的递归函数
*既然是全局变量，那又可以思考一个问题，为什么同样是全局变量，
*凭什么flag[]这个标志数组要还原为原来的值，而res不用
*玛雅人的密码那题，它的循环部分的代码：
*flag[]和str都是全局变量，都需要还原
    for(i=0;i<n-1;i++)//从头开始，挨个交换
    {
        if(flag[i]==0)
        {
            swap(&str[i],&str[i+1]);//交换过后，下次就不再交换，
                        //如ab 交换后为ba，若不标记下次就有要交换成ab
            flag[i]=1;//将该位置标记
            find(str,n,k+1);//此次交换过后，k++，进行下一轮判定
            swap(&str[i],&str[i+1]);//返回原状
            flag[i]=0;
        }
    }
*理由是str必须要还原，str是搜索过程中前后连贯使用的变量，必须还原
*而res是记录结果的数组，必然不能还原，需求不同，没有比较的必要哈哈
*/
/**
*解题调试过程：
*->编码
*->检查：
*    ①发现忘记将输入的字符进行排序qsort();
*    ②cmp的返回值有问题，忘记了传进来的是指针不是值，不能直接相减
*    ③cur未在main函数中清0，(通过思考res数组的初始值发现)
*    ④
*->编译：
*    错误：新增加的cur= 0;语句的分号达成了中文的分号，产生理由：不详
*    影响：2处error
*    修改后，自测实例通过
*->提交：输出格式不符合要求
*    查看别人的代码，发现每组样例输出结束后要再输出一个回车
*    理解错了样例的意思，以为是每一个排列
*    通过啦！！！开森，回宿舍洗澡去！！！
*/
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
int flag[6];
char res[7];
char ori[7];
int cmp(const void * p1, const void *p2){
    char * c1 = (char *)p1;
    char * c2 = (char *)p2;
    return (*c1 - *c2);//低类型可以自动转化为高类型，不需要(int)进行强制类型转换
}
int cur = 0;
/**
*深入优先搜索的递归算法
*参数：当前的深度，同时也作为数组的下标
*当然深度也可以作为全局变量，在递归调用后恢复原值
*那我就不要参数，使用后一个方法吧
*/
void DFS(){
    int len = strlen(ori);//其实len是一直不变的，
              //作为全局变量的话可以减少strlen()运算
         //不过全局变量的缺点是访问速度不如局部变量快，我暂时是这么认为的
    if(cur == len){ //递归的退出条件，当下标=(strlen(ori) - 1)+1
                    //这么写是为了表示字符串已经存完了，
                              //该存'\0'了，不存'\0'就不是字符串
                    //用%s输出就会出错啦
        res[cur] = '\0';
        printf("%s\n", res);
        return ;
    }
    int i;
    for(i = 0; i < len; i++){
        if(!flag[i]){ //如果没有被标记，元素未被使用
            flag[i] = 1;
            res[cur] = ori[i];
            cur ++;
            DFS();
            cur --;
            flag[i] = 0;
        }
    }
}
int main(){
    int n;
    while(scanf("%s", ori) != EOF){
        n = strlen(ori);
        cur = 0;
        qsort(ori, n, sizeof(char), cmp);
        while(n--) flag[n] = 0;
        DFS();
        printf("\n");
    }
    return 0;
}

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
 
string str;
string res;
bool used[6];
 
void Dfs(int cur)
{
    if (cur == str.length())
    {
        cout << res << endl;
        return;
    }
    for (int i = 0; i < str.length(); ++i)
    {
        if (!used[i])
        {
            //放入
            used[i] = true;
            res[cur] = str[i];
            Dfs(cur + 1);
            used[i] = false;
        }
    }
}
 
int main()
{
    while (cin >> str)
    {
        sort(str.begin(), str.end());
        res = str;
        memset(used, false, sizeof(used));
        Dfs(0);
        cout << endl;
    }
}

#include <bits/stdc++.h>
using namespace std;
int main(){
    for(string s;cin>>s;cout<<endl){
		sort(s.begin(),s.end());
		for(cout<<s<<endl;next_permutation(s.begin(),s.end());cout<<s<<endl);
    }
    return 0;
} 

//算法思想：全排列的n皇后问题思路，对问题进行递归实现。
//只不过将全排列的数字换为字母进行输出即可。
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=7;//P为当前排列，hashTable记录x是否已经在p中
int n,hashTable[maxn]={false};//当前处理排列的index位
char p[maxn];//储存全排列结果的数组
void generateP(int index,char str[])
{
    if(index==n)//递归边界
    {
        for (int i = 0; i <n; ++i)
        {
            printf("%c", p[i]);//输出当前排列
        }
        printf("\n");
        return;
    }
    for (int x = 0; x <n; ++x)//枚举1～n，试图将x填入p【index】
    {
        if (hashTable[x]==false)//如果x不在p[0]~p[index-1]中
        {
            p[index]=str[x];//令p的index位为先，即把str[x]加入当前排列
            hashTable[x]=true;//记x已经在p中
            generateP(index+1,str);//处理排列的index+1位
            hashTable[x]=false;//已处理完p[index]为x的子问题，还原状态
        }
    }
}
int main(int argc, char const *argv[])
{
    char str[maxn];
    while(scanf("%s",str)!=EOF)
    {
        n=strlen(str);
        sort(str,str+n);//将原始数组进行大小排序
        generateP(0,str);
        printf("\n");
    }
    return 0;
}

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

const int maxn = 7;

char site[maxn] = {0};
string str;

void solve(int num)
{
    if(num == str.length())
    {
        for(int i = 0; i < str.length(); ++i)
        {
            cout << site[i];
        }
        cout << endl;
    }
    else
    {
        int flag = 0;       // 判断是否出现过
        char tmp;
        for(int i = 0; i < str.length(); ++i)
        {
            // 判断是否出现过
            tmp = str[i];
            flag = 0;
            for(int j = 0; j < num; ++j)
            {
                if(site[j] == tmp)
                {
                    flag = 1;
                    break;
                }
            }
            if(flag == 1) continue;
            site[num] = str[i];
            solve(num+1);
        }
    }
}

int main()
{
    
    int count = 0;
    while(cin >> str)
    {
        sort(str.begin(), str.end());       // 按字典序输出
        solve(0);
        cout << endl;
    }

    return 0;
}

题目不严谨，题干中讲输入字符串已经排列，然而测试样例中给出了dbc的输入

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