字典序

Dear 丶 2024-02-19 16:38 63阅读 0赞

**一.字典序基础**

**字典序（dictionary order）**，又称 **字母序（alphabetical order）**，原意是表示英文单词在字典中的先后顺序，在计算机领域中扩展成两个任意字符串的大小关系。

英文中的 **字母表（Alphabet）** 按照如下的顺序排列：

ABCDEFG HIJKLMN OPQRST UVWXYZ

abcdefg hijklmn opqrst uvwxyz

在字典中，单词是按照首字母在字母表中的顺序进行排列的，比如 alpha 在 beta 之前。而第一个字母相同时，会去比较两个单词的第二个字母在字母表中的顺序，比如 account 在 advanced 之前，以此类推。下列单词就是按照字典序进行排列的：

aster

astrolabe

astronomy

astrophysics

ataman

attack

baa

在计算机领域中，这个字典序就不仅仅用来比较英文单词了，而是比较任意字符串。对于两个字符串，大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值的大小关系。比如`ah1x`小于`ahb`，而`Z5`小于`a3`。下列字符串就是按照字典序进行排列的：

\*(&%%\#

,.23

234q

A2.532

ZZRWA23

\\235

a/34

a423

h2ab\`.

在绝大多数语言中，都提供了比较两个字符串大小的方法，比较的实际上就是两个字符串的字典序。例如在 [C++ 语言][C_] 中：

cout << ("ah1x" < "ahb") << endl;

就会输出`true`，而在 [Java 语言][Java] 中：

System.out.println("ah1x".compareTo("ahb"));

会输出 -49−49，这个数是两个字符串第一个不一样的位置的两个字符的 ASCII 值之差，如果小于零则说明第一个字符串小于第二个字符串。

除此之外，大多数语言也都有对应的字符串比较方法，而背后的核心都是字符串的字典序。理解并掌握这个重要的概念，对今后计算机专业课程的学习和程序开发

二.字典序算法相关

1.字典序全排列问题

示例：`1 2 3`的全排列如下：

1 2 3 | 1 3 2 | 2 1 3 | 2 3 1 | 3 1 2 | 3 2 1

*  我们这里是通过字典序法找出来的。

那么什么是字典序法呢？

从上面的全排列也可以看出来了，从左往右依次增大，对这就是字典序法。可是如何用算法来实现字典序法全排列呢？

我们再来看一段文字描述：（用字典序法找`124653`的下一个排列）

*  如果当前排列是`124653`，找它的下一个排列的方法是，从这个序列中从右至左找第一个左邻小于右邻的数
 *  如果找不到，则所有排列求解完成，如果找得到则说明排列未完成
 *  本例中将找到`46`，计`4`所在的位置为`i`,找到后不能直接将`46`位置互换，而又要从右到左到第一个比`4`大的数
 *  本例找到的数是`5`，其位置计为`j`，将`i`与`j`所在元素交换`125643`
 *  然后将`i+1`至最后一个元素从小到大排序得到`125346`，这就是`124653`的下一个排列

下图是用字典序法找`1 2 3`的全排列（全过程）：

![SouthEast][]

**1、** **递归版本**

**算法简述**

简单地说：就是第一个数分别以后面的数进行交换

E．g：E = （a , b , c），则 prem（E）= a.perm（b,c）+ b.perm（a,c）+ c.perm（a,b）

然后a.perm（b,c）= ab.perm（c）+ ac.perm（b）= abc + acb.依次递归进行

Foo(const char *str)
    {    
     Perm( str , 0 , strlen( str ) – 1 );
    }
    //需要三个参数，k表示当前的数，m表示数的个数
    Perm( char *pszStr , int k , int m ) 
    {
          if (k == m)  
          {  
               static int s_i = 1;  
               cout<<” 第 ”<<s_i ++<<” 个排列  ”<<pszStr<<endl;
         }  
         else
         {  
               for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列
               {  
                      Swap(pszStr + k, pszStr + i);  
                      Perm(pszStr, k + 1, m);  
                      Swap(pszStr + k, pszStr + i);  
               }  
          } 
    }

去掉重复符号的全排列：在交换之前可以先判断两个符号是否相同，不相同才交换，这个时候需要一个判断符号是否相同的函数。

bool IsSwap(char *pszStr, int nBegin, int nEnd)  
    {  
           for (int i = nBegin; i < nEnd; i++) 
           if (pszStr[i] == pszStr[nEnd])  
                 return false;  
           return true;  
    }
    Perm(char *pszStr, int k, int m)  
    {  
         if (k == m)  
         {  
              Static int s_i = 1;  
              cout<<” 第 ”<<s_i ++<<” 个排列  ”<<pszStr<<endl;
         }  
         else
         {  
              for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列
              {  
                    if (IsSwap(pszStr, k, i))   //添加的判断语句，判断是否相等
                    {  
                          Swap(pszStr + k, pszStr + i);  
                          Perm(pszStr, k + 1, m);  
                          Swap(pszStr + k, pszStr + i);  
                    }  
               }  
          }  
    }

2.**非递归版本**

**算法简述**

要考虑全排列的非递归实现，先来考虑如何计算字符串的下一个排列。如"1234"的下一个排列就是"1243"。只要对字符串反复求出下一个排列，全排列的也就迎刃而解了。

如何计算字符串的下一个排列了？来考虑"926520"这个字符串，我们从后向前找第一双相邻的递增数字，"20"、"52"都是非递增的，"26 "即满足要求，称前一个数字2为**替换数**，替换数的下标称为**替换点**，再从后面找一个比替换数大的最小数（这个数必然存在），0、2都不行，5可以，将5和2交换得到"956220"，然后再将替换点后的字符串"6220"颠倒即得到"950226"。

如果达到这个数的最大，比如1234-à4321,这个时候就结束整个循环。

如果输入是一个非最小数，如1324，则将它转换为最小数，如1234，再进行排序。排序算法用快排，可以自己写一个，如果快排不会的话，就先看会再来接着看，或者自己想一个靠谱的算法，也可以直接用VC库中的qsort(s , n , sizeof(s\[0\]) , cmp);各参数是什么意思就自己在下面多花点时间吧。

Prem( char *s )   //全排列函数
    {
        char *pEnd = s + strlen(s) - 1;
        char *p = pEnd;  //p代表替换点
        //q代表替换点的下一个数 ，pMax 代表替换点后比替换点大的最小数
        char *q = new char,*pMax = new char;  //注意初始化！！！
        while (p !=  s)          //p == s 就结束循环
        {
            q = p;
            p--;
            if (*p < *q)
            {
                pMax = FindMaxForOne(p,pEnd);  //找与替换点交换的点
                Swap(p,pMax);         //交换
                Reverse(q,pEnd);       //将替换点后所有数进行反转
                Print(s);              //输出
                p = pEnd;             //将替换点置最后一个点，开始下一轮循环
            }
            if (s == p) break;           //结束条件
        }
    }
    char* FindMaxForOne(char *p,char *q)
    {
        char *p1 = p;
        char *p2 = q;
        while (*p2 <= *p1) p2--;
        return p2;
    }

二、字典序排序

例1：

> exp:  
> 6125431  
> 按照字典序，下一个数是哪个？

1.  寻找最后一对递增数AB（25）
2.  之后的最小但大于A的数与A调换（2&3）=>6135421
3.  之后的数反排（即从小到大排列）=>6131245

例2：

字典序排序

字符

#include<algorithm>
    #include<cstring>
    #include<cstdio>
    #define M  100000
    #define len 22
    using namespace std;
    char str[M][len];
    int cmp1(const void *a,const void*b){
        char *s1=(char *)a;
        char *s2=(char *)b;
        return strcmp(s1,s2);
    }
    int main()
    {
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%s",str[i]);
        qsort(str,n,sizeof(char)*len,cmp1);
        for()
        return 0;
    }

字符串

#include<algorithm>
    #include<cstring>
    #include<cstdio>
    #include<iostream>
    #define M  100000
    #define len 22
    using namespace std;
    string str[1005];
    int cmp(string a,string b)
    {
        return a.compare(b)<0;
    }
    int main()
    {
        int n;
        scanf("%d", &n);
        for (int i=0; i<n; i++)
            cin>>str[i];
        sort(str, str+n, cmp);
        return 0;
    }

结构体：

#include<algorithm>
    #include<cstring>
    #include<cstdio>
    #define M  100000
    #define len 22
    using namespace std;
    struct Word{
        char str[len];
    }word[M];
    int cmp(Word a,Word b)
    {
        return strcmp(a.str, b.str)>0;
    }
    int main()
    {
        int n;
        scanf("%d", &n);
        for (int i=0; i<n; i++)
            scanf("%s", word[i].str);
        sort(word, word+n, cmp);
        return 0;
    }

[C_]: https://www.jisuanke.com/course/cs112
[Java]: https://www.jisuanke.com/course/cs116
[SouthEast]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/dd91c4af53a940198c1bb5f1bd18bbf2.png