字典序 订阅
在数学中,字典或词典顺序(也称为词汇顺序,字典顺序,字母顺序或词典顺序)是基于字母顺序排列的单词按字母顺序排列的方法。 这种泛化主要在于定义有序完全有序集合(通常称为字母表)的元素的序列(通常称为计算机科学中的单词)的总顺序。对于数字1、2、3......n的排列,不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345,排列12345在前,排列12354在后。按照这样的规定,5个数字的所有的排列中最前面的是12345,最后面的是 54321。 展开全文
在数学中,字典或词典顺序(也称为词汇顺序,字典顺序,字母顺序或词典顺序)是基于字母顺序排列的单词按字母顺序排列的方法。 这种泛化主要在于定义有序完全有序集合(通常称为字母表)的元素的序列(通常称为计算机科学中的单词)的总顺序。对于数字1、2、3......n的排列,不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345,排列12345在前,排列12354在后。按照这样的规定,5个数字的所有的排列中最前面的是12345,最后面的是 54321。
信息
又    名
词典顺序
定    义
按字母顺序排列的方法
应用学科
数学
中文名
字典序
外文名
lexicographical order
相关术语
有序集合
字典序简单理解
设想一本英语字典里的单词,何者在前何者在后?显然的做法是先按照第一个字母、以 a、b、c……z 的顺序排列;如果第一个字母一样,那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长(比如,sigh 和 sight),那么把短者排在前。通过这种方法,我们可以给本来不相关的单词强行规定出一个顺序。“单词”可以看作是“字母”的字符串,而把这一点推而广之就可以认为是给对应位置元素所属集合分别相同的各个有序多元组规定顺序:下面用形式化的语言说明。
收起全文
精华内容
下载资源
问答
  • 字典序

    万次阅读 多人点赞 2019-01-25 10:45:56
    字典序基础 字典序(dictionary order),又称字母序(alphabetical order),原意是表示英文单词在字典中的先后顺序,在计算机领域中扩展成两个任意字符串的大小关系。 英文中的字母表(Alphabet)按照如下的顺序...

    一.字典序基础

    字典序(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;
    }
    
    展开全文
  • /***字典序全排列*字符串的全排列*比如单词"too" 它的全排列是"oot","oto","too"*1,从右端开始扫描,若出现前一个比后一个小,记录前一个的元素下表index*2,再找出index以后比该元素大的中的最小值的下标,(实现见 ...

    import java.util.Arrays;

    /**

    *字典序全排列

    *字符串的全排列

    *比如单词"too" 它的全排列是"oot","oto","too"

    *1,从右端开始扫描,若出现前一个比后一个小,记录前一个的元素下表index

    *2,再找出index以后比该元素大的中的最小值的下标,(实现见 下面的getMin方法)

    *3,index以后的元素实现反转(实现 见下面的reverse方法)

    *结束条件:前一个都比后一个大的情况

    */

    public class StringExpress{

    int getMin(char[]input,int index){

    char min=input[index];

    int minIndex=index+1;

    char result='z';

    for(int i=index+1;i

    if(input[i]>min&&input[i]

    result=input[i];

    minIndex=i;

    }

    }

    return minIndex;

    }

    void exchange(char []input,int index,int minIndex){

    char temp=input[index];

    input[index]=input[minIndex];

    input[minIndex]=temp;

    }

    void reverse(char input[],int first,int end) {

    while(first

    exchange(input,first,end);

    first++;

    end--;

    }

    }

    void getDictionary(char c[]){

    System.out.println(new String(c));

    //boolean flag=true;

    int i=0;

    while(true){

    i=c.length-1;

    for(;i>0;i--){

    if(c[i-1]

    }

    if(i==0)break;

    int minIndex=getMin(c,i-1);

    exchange(c,i-1,minIndex);

    reverse(c,i,c.length-1);

    System.out.println(new String(c));

    }

    }

    public static void main(String []args){

    String input="aat";

    char [] c=input.toCharArray();

    Arrays.sort(c);

    new StringExpress().getDictionary(c);

    }

    }

    展开全文
  • 排列的字典序 Time Limit:1000MS Memory Limit:65536K Total Submit:80 Accepted:22 Description n 个元素 { 1, 2, ..., n } 有 n! 个不同的排列. 将这 n! 个排列按字典序排列, 并编号为 0, 1, …, n!-1. 每个...
  • /*** 字典序的最小的问题* 给定长度为N的字符串s,要构造一个长度为N的字符串T,开始T是一个空的字符串,随后反复进行下列的操作** 从S的头部删除一个字符,添加到T的尾部* 从S的尾部删除一个字符,添加到T的尾部* ...

    package demo1;

    import java.util.Scanner;

    /**

    * 字典序的最小的问题

    * 给定长度为N的字符串s,要构造一个长度为N的字符串T,开始T是一个空的字符串,随后反复进行下列的操作

    *

    * 从S的头部删除一个字符,添加到T的尾部

    * 从S的尾部删除一个字符,添加到T的尾部

    * 不论顺序的执行上述的操作。

    * 构造一个尽量小的字符串。

    *

    *

    *

    * @author Administrator

    *

    */

    public class Main {

    public static void main(String[] args) {

    Scanner input = new Scanner(System.in);

    int N = input.nextInt();

    StringBuffer sb = new StringBuffer();

    String str = "";

    String T= "";

    for (int i = 0;i

    str = (sb.append(input.next())).toString();

    }

    //把字符串转化成数组

    char [] cs = str.toCharArray();

    int a= 0;//表示的是下标

    int b = N-1;//表示的是下标

    while (a <= b) {//将从左起和从右起的字符串进行比较

    boolean left = false;

    for (int i=0;a+i<=b;i++) {

    if (cs[a+i]

    left = true;

    break;

    }else if (cs[a+i] >cs[b-i]){

    left = false;

    break;

    }

    }

    if (left) {

    T+=cs[a++];

    }else {

    T+=cs[b--];

    }

    }

    System.out.println(T);

    }

    }

    展开全文
  • 字典序与字典树

    2021-02-25 11:22:33
    字典序则表示各字符对应位置排序的结果 题目描述 给定整数n和m, 将1到n的这n个整数按字典序排列之后, 求其中的第m个数。 对于n=11, m=4, 按字典序排列依次为1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9, 因此第4个数是2. ...

    字典树通常采取一个精简的结构来维护大量的单词集合,并保持有序以及对单词的统计
    字典序则表示各字符对应位置排序的结果

    题目描述
    给定整数n和m, 将1到n的这n个整数按字典序排列之后, 求其中的第m个数。
    对于n=11, m=4, 按字典序排列依次为1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9, 因此第4个数是2.
    对于n=200, m=25, 按字典序排列依次为1 10 100 101 102 103 104 105 106 107 108 109 11 110 111 112 113 114 115 116 117 118 119 12 120 121 122 123 124 125 126 127 128 129 13 130 131 132 133 134 135 136 137 138 139 14 140 141 142 143 144 145 146 147 148 149 15 150 151 152 153 154 155 156 157 158 159 16 160 161 162 163 164 165 166 167 168 169 17 170 171 172 173 174 175 176 177 178 179 18 180 181 182 183 184 185 186 187 188 189 19 190 191 192 193 194 195 196 197 198 199 2 20 200 21 22 23 24 25 26 27 28 29 3 30 31 32 33 34 35 36 37 38 39 4 40 41 42 43 44 45 46 47 48 49 5 50 51 52 53 54 55 56 57 58 59 6 60 61 62 63 64 65 66 67 68 69 7 70 71 72 73 74 75 76 77 78 79 8 80 81 82 83 84 85 86 87 88 89 9 90 91 92 93 94 95 96 97 98 99 因此第25个数是120…

    求解思路

    容易想到最简单的方式是将所有数字按照字典序排序,取得第m个即可,那么这些数字可以被组织在字典树中,字典树根节点包含1-9这些分支节点,往后的每个分支节点最多可能包含0-9共10个节点
    本问题不需要完整复现整个字典树,而只需要定位到所在分支即可

    其思路为首先研究第m个数第一个字符是什么?
    那么可以研究以1字符开头的数字总数count有多少(等价于1开头所在字典树子树的节点总数)
    若m<=count 那么在以1开头的子树中寻找,即转移到 1=> 10 m=m-1
    (若m即为1 那么输出当前开头串)
    若m>count 那么转移到当前1的兄弟节点研究 即 1=》2 m=m-count

    其核心的思路即为确定数字所在的子树,并通过下移或者右移缩小范围

    代码实现

    #include<iostream>
    #include<string>
    using namespace std;
    
    //计算pre打头的数的个数  其中n指最大的数
    
    long getPreCount(long pre,long n)
    {
        long count=1;//默认至少有一个pre
        long mutli=10;//倍数
        for(;pre*mutli<=n;mutli*=10)  //判断其扩大10倍是否会超出
        {
            if(pre*mutli+mutli-1<=n)  
                count+=mutli;
            else
                count+=n+1-pre*mutli;  //计算能够引入多少个
        }
        return count;
        //例如计算以1打头的数字  n=256
        //首先研究1*10+0<=256?  1*10+1<=256  ....1*10+9<256
        //接着研究 1*100+0<=256? 1*100+1<=256 ....1*100+99<256?
        //若满足 那么count+=10 count+=100
        //若不满足 那么研究能有多少个 可以使用
      
    }
    long fun(long n,long m)
    {
        long pre=1;//默认前序
        while(m!=0)
        {
            long count=0;
            count=getPreCount(pre,n);//计算当前pre所在分支的数量
            if(count>=m) //那么m就在该分支内寻找
            {
                m--;//去除pre
                if(m==0)  //那么之前为1 即为pre代表的数字
                    break;
                pre*=10;//下移到所在子树的第一个位置(分支0位置)
            }
            else
            {
                m-=count;  //跳过前面pre开头的部分 转移到pre+1
                pre++;    //移动到其兄弟节点
            }
    
        }
        
        return pre;//最终定位到的pre即第m个位置
      
    }
    
    int main()
    {
        
        long n,m;
        while(cin>>n>>m)
        {
            cout<<fun(n,m)<<endl;
        }
        return 0;
        
    
    }
    
    展开全文
  • java的字典序排序

    万次阅读 2016-01-25 00:07:27
    java中的字典序排序
  • Description在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表A由 26 个小写英文字母组成A={a,b,…,z}。...现在对字母表A 产生的所有长度不超过6 的升序字符串按照字典序排列并编码如下。 对于任...
  • 字典序算法

    2013-10-13 10:20:57
    适合面试,对学习算法的菜鸟有很大的帮助,同时企业面试也会考你字典序,只需要知道简单的字典序就足以应付考试
  • 字典序与标准序

    2020-09-29 10:41:44
    标准序与字典序 标准序:短的在前面,长的在后面,等长的依次比字母 to<up<cap<cat<too<two<boat<boot<card 字典序:依次比较字母,字母较大的在后面 boat<boot<cap<card&...
  • 链接:https://www.nowcoder.com/acm/contest/84/A来源:牛客网题目描述给定字符串s,s只包含小写字母,请求出字典序最大的子序列。子序列:https://en.wikipedia.org/wiki/Subsequence字典序:...
  • 首先看一下什么是字典序 我们的目的是给定一个数字n,首先构造range(1,n+1),即1,2,3......n的排列,然后生成一个字典序,代码如下: #!/usr/bin/python # coding:utf-8 def next_permutation(A): """ input...
  • 字典序排序

    千次阅读 2019-01-30 16:41:01
    主要是关于LeetCode当中的字典序排序问题 386 Lexicographical Numbers 440 字典序的第K小数字 524 通过删除字母匹配到字典里面最长单词 361 去除重复字母使得剩下的字典排序最小的情况 386 字典序排序算法 Given ...
  • 关于字典序

    2019-10-02 11:22:24
    又遇到字典序的题目了,于是仔细思考了下 通用方法 为了保证字典序最小,最通用的办法就是“我为人人”,倒过来考虑,顺着输出(也可以是顺着考虑,倒过来输出,反正两个方向不能相同) ... 因为倒过来考虑时,能...
  • 本文实例讲述了java实现对map的字典序排序操作。分享给大家供大家参考,具体如下:java中对map的字典序排序,算法验证比对微信官网https://mp.weixin.qq.com/wiki?t=resource/res_main&id=mp1421141115&...
  • 字典序问题

    2017-09-04 11:42:19
    字典序问题
  • 第一种:(字典序)#include #include #include int a[10],p[10],vis[10];//标记为1则说明已固定int n;void digui(int l){int i;if(l>n){for(i=1;iprintf("%d ",p[i]);}printf("%d\n",p[n]);}for(i=1;i<=n;i++){...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 24,900
精华内容 9,960
关键字:

字典序