在數學中，字典或詞典順序（也稱為辭彙順序，字典順序，字母順序或詞典順序）是基於字母順序排列的單詞按字母順序排列的方法。 這種泛化主要在於定義有序完全有序集合（通常稱為字母表）的元素的序列（通常稱為計算機科學中的單詞）的總順序。
對於數字1、2、3......n的排列，不同排列的先後關係是從左到右逐個比較對應的數字的先後來決定的。例如對於5個數字的排列 12354和12345，排列12345在前，排列12354在後。按照這樣的規定，5個數字的所有的排列中最前面的是12345，最後面的是 54321。
基本介紹
- 中文名：字典序
- 外文名：lexicographical order
- 又名：詞典順序
- 定義：按字母順序排列的方法
- 相關術語：有序集合
- 套用學科：數學
簡單理解,形式定義,多個集合乘積,描述,程式源碼,算法說明,
簡單理解
構想一本英語字典里的單詞，何者在前何者在後？
顯然的做法是先按照第一個字母、以 a、b、c……z 的順序排列；如果第一個字母一樣，那么比較第二個、第三個乃至後面的字母。如果比到最後兩個單詞不一樣長（比如，sigh 和 sight），那么把短者排在前。
通過這種方法，我們可以給本來不相關的單詞強行規定出一個順序。“單詞”可以看作是“字母”的字元串，而把這一點推而廣之就可以認為是給對應位置元素所屬集合分別相同的各個有序多元組規定順序：下面用形式化的語言說明。
形式定義
- (a,b) ≤ (a′,b′) 若且唯若a<a′ 或 (a=a′ 且b≤b′).
結果是偏序。如果A和B是全序, 那么結果也是全序。
多個集合乘積
上面的定義可以拓展：只要兩個元素屬於 A×B×...×N 這個笛卡爾積，或曰可寫成 T1=(a1, b1, ..., n1) 和 T2=(a2, b2, ..., n2) 的有序多元組形式，那么兩者即可排序——從前往後：
- 如果 a1 和 a2 沒有順序（按照 A 上的偏序，下同）：那么 T1 和 T2 沒有順序。
- 否則，如果 a1 在 a2 之前，那么 T1 在 T2 之前；反之若 a2 在 a1 之前，那么 T2 在 T1 之前。
- 否則 a1 和 a2 不分先後。接下來討論 b1/b2、c1/c2 等等。
T1 和 T2 甚至可以不一樣長：只要對應位置的元素所屬的集合相同（第一個位置的元素都屬於 A 集合、第二個位置的元素都屬於 B 集合、等等），即可套用上面的做法。如果比到後面發現兩者之一的元素先耗盡了，那么可視情況規定短者排在前或在後。
回到英語單詞的例子上來。單詞可以說是在笛卡爾積 A×A×A×... 這個集合（其中集合 A 是二十六個英文字母的集合，注意組成笛卡爾積的這些集合不必彼此不同）上的多元組，那么在字典中排列單詞的順序就是這裡說的字典序——這也就是“字典序”這個名稱的由來。
描述
字典序如下：
設P是1～n的一個全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn
1）從排列的右端開始，找出第一個比右邊數字小的數字的序號j（j從左端開始計算），即 j=max{i|pi<pi+1}
2）在pj的右邊的數字中，找出所有比pj大的數中最小的數字pk，即 k=max{i|pi>pj}（右邊的數從右至左是遞增的，因此k是所有大於pj的數字中序號最大者）
3）對換pj，pk
4）再將pj+1......pk-1pkpk+1......pn倒轉得到排列p'=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，這就是排列p的下一個排列。
程式源碼
#include"stdio.h"#include"string.h"int *MediumToPermutation(int *piMedium,int iLen){int *pFlag;inti,j,sum;int *piPermutation;piPermutation=new int[iLen+1];pFlag=new int[iLen+1];memset(pFlag,0,sizeof(int)*(iLen+1));for(i=0;i<iLen;i++){j=0;sum=0;while(j<iLen+1){if(pFlag[j]==0)sum+=1;if(sum>piMedium[i])break;j++;}pFlag[j]=1;piPermutation[i]=j+1;}for(i=0;i<iLen+1;i++){if(pFlag[i]==0){piPermutation[iLen]=i+1;break;}}delete[]pFlag;returnpiPermutation;}int*PermutationToMedium(int*piPermutation,intiLen){inti,j,sum;int*piMedium;piMedium=newint[iLen-1];memset(piMedium,0,sizeof(int)*(iLen-1));for(i=0;i<iLen-1;i++){j=i+1;while(j<iLen){if(piPermutation[i]>piPermutation[j])piMedium[i]++;j++;}}returnpiMedium;}voidNextM(int*piMedium,intiLen,intiM){inti,iAdd;while(iM>0){iAdd=2;piMedium[iLen-1]=piMedium[iLen-1]+1;for(i=iLen-1;i>0;i--){if(piMedium[i]==iAdd){piMedium[i]=0;piMedium[i-1]=piMedium[i-1]+1;}elsebreak;iAdd++;}}if(i==0){if(piMedium[0]==iAdd){for(i=0;i<iLen;i++){piMedium[i]=iLen-i;}break;}}iM--;}int*Solve(int*piPermutation,intiLen,intiNext){int*piResult;int*piTmp;inti;piTmp=PermutationToMedium(piPermutation,iLen);printf("對應的中介數是：");for(i=0;i<iLen-1;i++)printf("%d",piTmp[i]);printf("\n");NextM(piTmp,iLen-1,iNext);printf("其後第%d個排列對應的中介數是：",iNext);for(i=0;i<iLen-1;i++)printf("%d",piTmp[i]);printf("\n");piResult=MediumToPermutation(piTmp,iLen-1);delete[]piTmp;returnpiResult;}voidCharToInt(char*pcIn,int*piOut){inti,j,n;inttmp[128]={0};intlen=strlen(pcIn);for(i=0;i<len;i++){tmp[pcIn[i]]=1;}n=1;for(i=0;i<128;i++){if(tmp[i]==1){for(j=0;j<len;j++){if(i==pcIn[j]){piOut[j]=n;n++;break;}}}}}voidIntToChar(char*pcCmp,int*piCmp,int*piIn,char*pcOut){inti,j;intlen=strlen(pcCmp);for(i=0;i<len;i++){for(j=0;j<len;j++){if(piCmp[j]==piIn[i]){pcOut[i]=pcCmp[j];break;}}}pcOut[len]='\0';}intmain(){//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);charin[128];intnext;printf("<===================作業二（全排列的生成算法）===================>\n");printf("請輸入排列字元串：");while(scanf("%s",in)!=EOF){printf("預推出其後的第幾個排列：");scanf("%d",&next);printf("排列%s",in);int*out;out=newint[strlen(in)];CharToInt(in,out);int*out1;inti;char*out2;out2=newchar[strlen(in)+1];out1=Solve(out,strlen(in),next);IntToChar(in,out,out1,out2);printf("排列%s後的第%d個排列是：",in,next);printf("%s\n",out2);printf("\n");delete[]out1;delete[]out2;delete[]out;}return 0;}