字典序

一.字典序基础

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

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

ABCDEFG HIJKLMN OPQRST UVWXYZ

abcdefg hijklmn opqrst uvwxyz

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

as

aster

astrolabe

astronomy

astrophysics

at

ataman

attack

baa

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

$

*(&%%#

,.23

234q

A2.532

ZZRWA23

\235

a/34

a423

h2ab`.

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

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

就会输出true，而在 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的全排列（全过程）：

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