序数法:一种排列的生成算法

序数法:一种排列的生成算法

一个\([ 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

发表评论

电子邮件地址不会被公开。 必填项已用*标注