序数法：一种排列的生成算法
一个\([ 0, n!-1] \)当中的整数m，先将其转化为唯一确定的长度 n-1 的序数\( (a_{n-1},…a_1) \)，再将这个序数转化为长度为n的一个排列。
下边详细介绍此方法和理论：
首先
\[\begin{align}
n! &= n(n-1)! \\
&= ((n-1)+1)(n-1)! \\
&= (n-1)(n-1)! + (n-1)!
\end{align}
\]
类似地，
\[(n-1)! = (n-2)(n-2)! + (n-2)!
\]
将上式代入最后一项，并运用多次则得：
\[\begin{align}n! &= (n-1)(n-1)! + (n-2)(n-2)! + (n-3)(n-3)! +… + 2 \cdot 2! + 1 \cdot 1! +1 \\ &=\sum_{k=1}^{n-1}{k \cdot k!} +1 \end{align} \]
那么0到\( n!-1 \)的整数m可以唯一地表示为：
\[m = a_{k-1}(k-1)! + a_{k-2} (k-2)! +… + a_2 \cdot 2! + a_1\]其中\( a_k \)满足\( 0 \le a_k \le k ,i=1,2,…,k-1 \)。
这样的话，0到\( n!-1 \) 的这n个整数就可与序数\( (a_{n-1},a_{n-2},…,a_2,a_1) \)建立一一对应关系。
接下来就讨论从整数m来计算序数 \( (a_{n-1},a_{n-2},…,a_2,a_1) \) 的过程:
\[ m= a_{n-1}(n-1)! + a_{n-2}(n-2)! +… + a_2 \cdot 2! + a_1 \]若记\( n_1 = m \)，令\( n_1 \)除以2，余数\( r_1 \)就是\( a_1 \) :
\[ n_2 = \lfloor \frac{n_1}{2} \rfloor = a_{n-1} \frac{(n-1)!}{2} + a_{n-2} \frac{(n-2)!}{2}+… + a_2, r_1 = a_1 \]\( n_2 \)继续除以3，余数就是\( a_2 \)
\[n_3 = \lfloor \frac{n_2}{3} \rfloor = a_{n-1} \frac{(n-1)!}{3!} + a_{n-2} \frac{(n-2)!}{3!}+… + a_3, r_2 = a_2 \]推及一般并可证，有\[n_{i+1} = \lfloor \frac{n_i}{i+1} \rfloor, r_i = a_i, i=1,2,…,n-1\]
也就是说，对于一个正整数m，不断的按照上式求出n-1个余数，就可以知道m唯一对应的序数。
例如：\( 7!>4000 \) ,以 \( m=4000 \) 为例，计算4000所对应的6位的序数
\[\begin{align}
n_1 &= 4000 \\
n_2 &= \lfloor\frac{4000}{2}\rfloor =2000,& a_1 =4000 \mod 2 = 0\\
n_3 &= \lfloor\frac{2000}{3}\rfloor =666,& a_2 = 2000 \mod 3 = 2\\
n_4 &= \lfloor\frac{666}{4}\rfloor =166,& a_3 = 666 \mod 4 = 2\\
n_5 &= \lfloor\frac{166}{5}\rfloor =33,& a_4 = 166 \mod 5 = 1\\
n_6 &= \lfloor\frac{33}{6}\rfloor =5,& a_5 = 33 \mod 6 = 3\\
n_7 &= \lfloor\frac{5}{7}\rfloor = 0,& a_6 =5 \mod 7 = 5
\end{align}\]
所以 \( 4000 = 5\cdot 6! + 3\cdot 5! + 1\cdot4! + 2\cdot3! + 2\cdot 2! \),序数为\( (5,3,1,2,2,0) \)
接下来就是要将序数 \( (a_{n-1},a_{n-2},…,a_2,a_1) \) 与n个元素的全排列一一对应。不失一般性，n个元素不妨令\( i \)为\( 1,2,…n \) ：序数 \( (a_{n-1},a_{n-2},…,a_2,a_1) \) 中\( a_i \)表示在排列中 \( i+1 \)这个数的右方比\( i+1 \) 小的数的个数,\( i=n-1,n-2,…,2,1 \)。
以4的全排列\( (1,2,3,4) \) 的一个序数\( (301) \)为例，\( a_3=3 \)，说明4这个数右方比4小的有3个，则4在第1位，a_2=0说明3这个数右方没有比3小的，则3在第4位，a_1=1说明2的右边有1个比2小的，所以2的右边有1。这样就可以确定这个排列为\( (4,2,1,3) \)
将此描述中的“右方”描述成“左方”，同样可以得到一种对应关系。
将m转化为序列seq[ (N-1) .. 1]. seq[i]的下标i代表序数\( a_i \)的下标i
void int2seq(int m,char* seq,int N)
{
int i,n_curr,n_next;
n_curr = m;
for(i=1;i<N;i++)
{
n_next = n_curr/(i+1);
seq[i] = n_curr % (i+1);
n_curr = n_next;
}
}将序数seq转化为一个1,2,3,…,n的排列
void seq2arrange(char *seq,char *arrange,int N)
{
int i,t,idx,counter;
memset(arrange,1,sizeof(char)*N);
for(i=N-1;i>=1;i--)
{
idx=N-1;
counter = seq[i];
while ( counter > 0)
{
if( arrange[idx]<i+1 )
{
counter -=1;
}
idx--;
}
while( arrange[idx]>1)
{
idx--;
}
arrange[idx] = i+1;
}
}main函数测试用：
int main(void)
{
int i,k,N;
char res[MAXN],seq[MAXN];
N=4;
for(i=0;i<fact(N);i++)
{
int2seq(i,seq,N);
seq2arrange(seq,res,N);
for(k=0;k<N;k++)
{
printf("%d",res[k]);
}
puts("");
}
return 0;
}运行结果
1234
2134
1324
2314
3124
3214
1243
2143
1342
2341
3142
3241
1423
2413
1432
2431
3412
3421
4123
4213
4132
4231
4312
4321