错排（公式+三种生成）

2018-08-16

公式

普通阶乘

$$
D_n=|I|-\sum_{i=1}^n|S_i|+\sum_{i=1}^n\sum_{j>i}|S_i∩S_j|-\sum_{i=1}^n\sum_{j>i}\sum_{k>i}|S_i∩S_j∩S_k|+…+(-1)^{n-1}|S_1∩S_2∩…∩S_n|
$$

$$
=n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+…+(-1)^{n}\frac{1}{n!})
$$

递推关系

$$
D_n=(n-1)(D_{n-1}+D_{n-2}),D_1=0,D_2=1
$$

$$
D_n=nD_{n-1}+(-1)^n
$$

三种生成方式

递归

时间复杂度为$O(D_n)$，但是由于递归函数的调用开销是很大的，系统要为每次函数调用分配存储空间，并将调用点压栈予以记录。而在函数调用结束后，还要释放空间，弹栈恢复断点。所以，考虑函数处理过程，整体看来，递归法的效率并不高。

void Digui(int n,int cur,int vis[]) //递归
{
    if(cur>n)
    {
        copy(a+1,a+n,ostream_iterator<int>(cout," "));
        cout<<a[n]<<endl;
        num1++;return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i]&&cur!=i)
        {
            vis[i]=1;a[cur]=i;
            Digui(n,cur+1,vis);
            vis[i]=0;
        }
    }
}

字典序生成法

用全排列的字典序生成法，同时对每次生成的全排列检验是否合法。

时间复杂度$O(2n*n!)$

void Dictionary(int n) //字典生成
{
    for(int i=1;i<=n;i++)
        b[i]=i;
    do{
        int flag=0;
        for(int i=1;i<=n;i++)
            if(b[i]==i)
            {
                flag=1;break;
            }
        if(flag) continue;
        num2++;
        copy(b+1,b+n,ostream_iterator<int>(cout," "));
        cout<<b[n]<<endl;
    }while(next_permutation(b+1,b+1+n));
}

改进的字典序生成法

在对于某一个生成的全排列时判断，同时对接下来不正确的全排列都跳过。由于这种额外的判断方式，我们不能再使用next_permutation函数。

时间复杂度$O(D_n)$

int AdLxOrder(int n)
{
    int num_a = 0;
    int *dearr = new int[n + 1];
    int *occup = new int[n + 1];
    int Flag = n + 1; //记录不满足错排的元素位置，均满足则为n+1
    for (int i = 0; i <= n; i++){ dearr[i] = 0;occup[i] = 0;}
    for (int i = 1, len = 0; i <= n + 1; i++)
    {
        if (i < n)                            //安排第i个位置
        {
            for (int j = 1; j <= n; j++)    //安排第i个位置
            {
                if (occup[j] == 0 && j != i)
                {
                    occup[j] = 1;            //occup[j]记录j是否已经被安排
                    dearr[i] = j;            //安排dearr[i]
                    break;
                }
            }
        }
        else if (i == n)                    //安排最后一位
        {
            for (int j = 1; j <= n; j++)    //安排第i个位置，无论是否满足
            {
                if (occup[j] == 0)
                {
                    occup[j] = 1;            //occup[j]记录j是否已经被安排
                    dearr[i] = j;
                    if (j == i)
                        Flag = n;
                    break;
                }
            }
        }
        else                                //i == n+1
        {
            if (Flag == n + 1)                //满足，输出，并找字典序下一个
            {
                num_a++;
                for(int k = 1;k <= n; k++)
                    printf("%d  ",dearr[k]);
                printf("\n");
                int pos = 0;
                for (int k = n; k > 1; k--)    //从右往左找下降
                {
                    if (dearr[k - 1] < dearr[k])
                    {
                        pos = k - 1;
                        for (int m = n; m > pos; m--)
                        {
                            if (dearr[m] > dearr[pos])    //找到后缀中较大的最小元素
                            {
                                if (dearr[m] == pos)
                                    Flag = pos;     //记录不满足的位置
                                int tmp = dearr[m];   //交换
                                dearr[m] = dearr[pos];
                                dearr[pos] = tmp;
                                //记录不满足的位置（只记录最左侧）
                                for (int k1 = pos+1, k2 = n; k1 < k2; k1++, k2--)
                                {
                                    if (dearr[k1] == k2 && Flag > k2)
                                        Flag = k2;  //记录不满足的位置
                                    if (dearr[k2] == k1 && Flag > k1)
                                        Flag = k1;  //记录不满足的位置

                                    int tmp = dearr[k2]; //陆续交换
                                    dearr[k2] = dearr[k1];
                                    dearr[k1] = tmp;
                                }
                                i = n; //循环末尾有i++，此处特取n
                                break;
                            }
                        }
                        break;
                    }
                }
            }
            else                            //找关键位置的下一个值
            {                                //关键位置：下降位置和不满足位置的最左者
                int pos = 0;
                for (int k = n; k > 1; k--)    //从右往左找下降
                {
                    if (dearr[k - 1] < dearr[k])
                    {
                        pos = k - 1;
                        if (pos > Flag)        //pos取下降位置和不满足位置的最左者
                            pos = Flag;

                        for (int m = pos; m <= n; m++) occup[dearr[m]] = 0; //全部重置
                        for (int m = dearr[pos] + 1; m <= n; m++) //从dearr[pos]+1开始找
                        {
                            if (occup[m] == 0 && m != pos) //给pos找到下一个值
                            {
                                dearr[pos] = m;
                                occup[m] = 1;
                                i = pos;
                                Flag = n + 1;
                                break;
                            }
                        }
                        if (Flag == n + 1)
                            break;
                        else
                            k = pos + 1;    //重新向前找下降，循环末尾有k--，此处特+1
                    }
                }
            }
        }
    }
    delete []dearr;
    delete []occup;
    return num_a;
}