一.字典序基础

字典序(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,将ij所在元素交换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;
}
Logo

旨在为数千万中国开发者提供一个无缝且高效的云端环境,以支持学习、使用和贡献开源项目。

更多推荐