字典序

数字也可以作为特别的字符串...这种情况下...如果我们用字典序进行比较...就有可能会出现下面这种情况...

"100"<"1000"..(加引号的目的是为了区别数字..与数字串..)

事实上呢.在计算机里...我们会这么看..和之前一样...我们会首先比较第一个字符...

这里"1"='1'..(已经可以看到区别了..在数中..数字因为位置的不同会有不同的意义..而这里.这种分别变的不一样了...)

..一步比较...还没有办法分辨出它们的大小...只好再比较之后的数...

这种情况回直到最后一次尝试...第一个字符串已经空掉之前...

如果硬要比较的话...

空格的ascii码值是32.(Ascii码还是用两位十六进制表示比较合适)

‘0’的ASCII码值是48 所以‘100’<'1000'

例子：依次比字母, 如boat < boot <

cap < card < cat < to < too< two < up

字典序法

对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是 54321。

字典序如下：

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

int i, j, sum;

int*piPermutation;

piPermutation= new int[iLen + 1];

pFlag = newint[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, int iLen)

{

int i, 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;

}

void NextM(int* piMedium, int iLen, int iM)

{

int i, 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;

}

else break;

iAdd++;

}

if(i== 0)

{

if(piMedium[0] == iAdd)

{

for(i = 0; i < iLen; i++)

{

piMedium[i] =iLen - i;

}

break;

}

}

iM--;

}

}

int* Solve(int* piPermutation, int iLen, int iNext)

{

int* piResult;

int*piTmp;

int i;

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;

}

void CharToInt(char* pcIn, int* piOut)

{

int i, j, n;

int tmp[128] ={0};

int len =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;

}

}

}

}

}

void IntToChar(char* pcCmp, int* piCmp, int* piIn, char*pcOut)

{

int i, j;

int len =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';

}

int main()

{

//freopen("input.txt", "r", stdin);

//freopen("output.txt","w", stdout);

char in[128];

int next;

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;

int i;

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个全排列，因此速度非常快。它的缺点是在生成序号（m-1）的递增进进制数时，需要事先创建一个用来存储n的阶乘数n! 的数组p[]，所以n的值不能太大，否则就会溢出，根据我的测试结果，当1<=n<=20时不会溢出，当21<=n时会溢出。

设置了中介数的字典序全排列生成算法需要设置中介数，在实际应用中比较繁琐，不如由前一个排列直接推得下一个排列方便。