全排列算法

全排列的定义见全排列.
这里我们详细讲一下交换法和字典序法

交换法

举个简单的例子，假设我们要对1234进行全排列
1.首先保证1不变，对234进行全排列
同样的，对234进行全排列可以保证2不变，对34进行全排列，然后保证3不变，对4进行全排列，因为4只有一个数，所以全排列只有一种，然后我们就得到了

2.这样我们就得到了以1开头的所有全排列，接下来就是得到分别以2，3，4开头的全排列了
只要我们将1与2，3，4分别交换，就分别得到了以2，3，4开头的初始序列。

代码

#include<iostream>
using namespace std;
int arr[5]={0,1,2,3,4};
void swap(int x,int y)//用于交换数组的两个数
{
    int temp=arr[x];
    arr[x]=arr[y];
    arr[y]=temp;
}
int resove(int n)//递归函数
{
        if(n==5)//当尝试对不存在的数组元素进行递归时，标明所有数已经排列完成，输出。
        {
            for(int i=0;i<5;i++)
            cout<<arr[i]; 
            cout<<endl;
            return 0;
        }
        for(int i=n;i<5;i++)//循环实现交换和之后的全排列  
        {//i是从n开始 i=n;swap(n,i)相当于固定当前位置，在进行下一位的排列。
            swap(n,i);
            resove(n+1);
            swap(n,i); 
        }
         
}
int main()
{
    resove(0);
}

如果初始序列中有重复元素的话，只要去重就可以了


bool isSwap(int begin,int end)
{
for(int i=begin;i<end;i++)
{
if(arr[i]==arr[end])
return false;
return true;
}
}
然后在循环的时候加上这个条件就行了。
for(int i=n;i<5;i++)//循环实现交换和之后的全排列  
        {//i是从n开始 i=n;swap(n,i)相当于固定当前位置，在进行下一位的排列。
               if(isSwap(n,i))
          {
            swap(n,i);
            resove(n+1);
            swap(n,i); 
           }
        }

可能你已经发现了，这样的输出是没有顺序的，如果我们要求输出必须按照字典序输出的话，这样显然是不可以的。所以接下来介绍一种字典序法。

字典序法

直接看代码吧，我也不知道咋解释

#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;
}

注意，字典序法要求输入的也是一个有序列。
今天在推荐一首歌，过客，挺好听的

全排列算法

交换法

代码

字典序法

推荐阅读更多精彩内容