-
字典序
鎖定
在數學中，字典或詞典順序（也稱為詞彙順序，字典順序，字母順序或詞典順序）是基於字母順序排列的單詞按字母順序排列的方法。 這種泛化主要在於定義有序完全有序集合（通常稱為字母表）的元素的序列（通常稱為計算機科學中的單詞）的總順序。
對於數字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 是二十六個英文字母的集合，注意組成笛卡爾積的這些集合不必彼此不同）上的多元組，那麼在字典中排列單詞的順序就是這裏説的字典序——這也就是“字典序”這個名稱的由來。
舉例來説，全排列{1,2,3} 按照字典序的下一個排列分別是 123、132、213、231、312 和 321。如果就數字集合 {1, 2, 3, ..., n} 的排列而言，這個集合的全排列本身可以看成是 n進制的數，這種情況下，所有排列的字典序等價於所有按照全排列順序把數字寫成的數集合的升序。
字典序描述
設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;
}
字典序算法説明
設置了中介數的字典序全排列生成算法，與遞歸直接模擬法和循環直接模擬法的最大不同是，不需要模擬有序全排列的生成過程，也就不需要逐一地生成各個全排列，只要知道初始全排列，就能根據序號（m-1），直接得到第m個全排列，因此速度非常快。
[2]
它的缺點是在生成序號（m-1）的遞增進進制數時，需要事先創建一個用來存儲n的階乘數n! 的數組p[]，所以n的值不能太大，否則就會溢出，根據我的測試結果，當1<=n<=20時不會溢出，當21<=n時會溢出。
設置了中介數的字典序全排列生成算法需要設置中介數，在實際應用中比較繁瑣，不如由前一個排列直接推得下一個排列方便。
