字典序算法笔记

---

一、相关概念介绍

1. 字典序
   字典序就是按照字典中出现的顺序对字符进行排序。
2. 全排列
   给定多个字符，可以按照任意顺序进行排列，所有排列称为全排列。例如字符串“abc”的全排列包括：“abc”、“cab”、“cba”、“bca”、“bac”、“acb”。
3. 字典序全排列
   对于给定多个字符的全排列里，每一种排列对应一个字符串，如果这些字符串按照字符串大小的顺序进行排序，那么就这种排序是基于字典序的全排列，也就是对给定字符的全排列按照字典序进行排序。例如字符串“abc”基于字典序的全排列为：abc > acb > bac > bca > cab > cba.

二、字典序算法

对于给定的字符串，通过sort排序能得到基于字典序的第一个排列，例如bca基于字典序的第一个排列为abc，剩下的问题转化为对于给定的排列，求基于字典序的下一个排列，例如abc基于字典序的下一个排列为acb，以此类推可以得到基于字典序的最后一个排列为cba。
对于给定排列，求基于字典序的下一个排列的算法流程如下：

1. 从右往左，找出第一个左边元素值小于右边元素值的位置，下标记作j，也就是第一次出现arry[j]<arry[j+1]；
2. 在位置j的右边部分，找出在所有大于arry[j]的数中最小的一个，将其下标记作k。实际上根据第一步的结果可以知道在j右边的部分，是从右往左递增的，因此这里只用在从右往左，找到第一个位置k，使其满足array[k]>array[j]；
3. 交换j和k两个位置的数；
4. 反转位置j右边的部分；

C++实现

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> res;
        res.clear();
        if(str.length()<1) return res;
        sort(str.begin(),str.end()); //经过排序得到基于字典序的第一个排列
        res.push_back(str);
        int len=str.length();
        int j,k;
        while(true){
            //从右往左，在相邻的两个数中，找出第一个左边小于右边的数，记下标为j
            for(j=len-2;j>=0 && str[j]>=str[j+1];--j) ;
            //j<0，说明当前序列就是字典序的最后一个排列，结束寻找过程
            if(j<0) break;
            //从右往左找到第一个大于str[j]的数，下标记为k
            for(k=len-1;k>j && str[k]<=str[j];--k) ;
            //交换j、k两个位置的数
            swap(str[j],str[k]);
            //对位置j右边的子序列进行反转操作
            reverse(str.begin()+j+1,str.end());
            //得到新的排列，放进结果集
            res.push_back(str);
        }
        return res;
    }
};

---

对于给定序列，求其基于字典序排列的下一个更大的排列，在C++的STL算法中有现成的封装可以使用，即bool next_permutation(BidirectionalIterator first, BidirectionalIterator last),该函数将[first,last]范围内的元素重新排列到下一个按字典顺序更大的排列中，如果按照字典序找不到比当前排列更大的序列，就返回false，并置当前排列为字典序的最小排列，否则返回true。

C++实现如下：

class Solution2 {
public:
    vector<string> Permutation(string str) {
        vector<string> res;
        if(str.length()<1) return res;
        sort(str.begin(),str.end()); //得到基于字典序的最小排列
        res.push_back(str);
        //在最小排列上，寻找基于字典序的更大排列
        while(next_permutation(str.begin(),str.end())) res.push_back(str);
        //跳出while循环表示已经找不到更大的排列了。
        return res;
    }
};

---

与bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)相反，STL的算法bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last)对于当前的排列，如果在字典序中还存在前一个排列，返回真，并且将前一个排列赋予当前排列，如果不存在，就把当前排列进行递减排序,也就是返回false时，返回的时字典序的最大排列。

//按字典序逆序求排列
class Solution3 {
public:
    vector<string> Permutation(string str) {
        vector<string> res;
        if(str.length()<1) return res;
        //反向迭代，通过排序找到基于字典序的最大排列
        sort(str.rbegin(),str.rend());
        //通过反转找到基于字典序的最大排列
        //reverse(str.begin(),str.end());
        res.push_back(str);
        //寻找基于字典序比当前排列更小的排列
        while(prev_permutation(str.begin(),str.end())) res.push_back(str);
        //跳出while循环表示已经找不到字典序更小的排列了
        //返回false时，返回的是字典序的最大排列
        return res;
    }
};

---

完整代码：

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

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> res; //结果集
        res.clear();
        if(str.length()<1) return res;
        sort(str.begin(),str.end()); //排序后得到基于字典序的第一个排列
        res.push_back(str);
        int len=str.length();
        int j,k;
        while(true){
            //从右往左，在相邻两个数中，找到第一个左边小于右边的数，用j记录其位置
            for(j=len-2;j>=0 && str[j]>=str[j+1];--j) ;
            //j<0，说明当前序列就是字典序的最后一个排列
            if(j<0) break;
            //从右往左，找到第一个大于str[j]的数，用k记录其位置
            for(k=len-1;k>j && str[k]<=str[j];--k) ;
            //交换j、k两个位置的数
            swap(str[j],str[k]);
            //对位置j右边子序列进行反转操作
            reverse(str.begin()+j+1,str.end());
            //将求得的新排列放入结果集中
            res.push_back(str);
        }
        return res;
    }
};

/*调用STL中的bool next_permutation(BidirectionalIterator first,BidirectionalIterator last)函数
该函数将[first,last]范围内的元素重新排列到下一个按字典顺序更大的排列中，如果
找不到比当前排列更大的排列，就返回false，否则返回true。
*/
class Solution2 {
public:
    vector<string> Permutation(string str) {
        vector<string> res;
        if(str.length()<1) return res;
        //通过排序找到基于字典序的最小排列
        sort(str.begin(),str.end());
        res.push_back(str);
        //寻找基于字典序比当前排列更大的排列
        while(next_permutation(str.begin(),str.end())) res.push_back(str);
        //跳出while循环表示已经找不到字典序更大的排列了
        //返回false时，返回的时字典序的最小排列
        return res;
    }
};

//按字典序逆序求排列
class Solution3 {
public:
    vector<string> Permutation(string str) {
        vector<string> res;
        if(str.length()<1) return res;
        //反向迭代，通过排序找到基于字典序的最大排列
        sort(str.rbegin(),str.rend());
        //通过反转找到基于字典序的最大排列
        //reverse(str.begin(),str.end());
        res.push_back(str);
        //寻找基于字典序比当前排列更小的排列
        while(prev_permutation(str.begin(),str.end())) res.push_back(str);
        //跳出while循环表示已经找不到字典序更小的排列了
        //返回false时，返回的是字典序的最大排列
        return res;
    }
};

void display(vector<string> s)
{
    int i;
    for(i=0;i<s.size();++i){
        cout<<s[i]<<endl;
    }
}

int main(int argc,char **argv)
{
    cout<<"字典排序结果："<<endl;
    string str="bca";
    Solution sol;
    vector<string> res;
    res=sol.Permutation(str);
    display(res);

    cout<<"调用STL的next_permutation()结果："<<endl;
    Solution2 sol2;
    vector<string> v2;
    v2=sol2.Permutation(str);
    display(v2);

    cout<<"调用STL的prev_permutation()结果(字典序逆序排列)："<<endl;
    Solution3 sol3;
    vector<string> v3;
    v3=sol3.Permutation(str);
    display(v3);

    return 0;
}

运行结果