Bell Ringing (全排列的邻位构造法)

2018-08-02

Bell Ringing

用生成全排列的邻位互换法：（具体方法解释可以看排列组合的文章）

仔细想想不就是把n插入到已完成的n-1阶排列的不同位置中得到n阶排列吗？

n=1; 1

n=2; 12 , 21

n=3; 123, 132, 312, 321, 231, 213

……

用这种方法可以产生出任意n阶全排列，（而且符合bellring中的移动规律，即每个数移动的位置最多为1，就能一下子构造出n！个不重复的全排列）

看！代码

#include <bits/stdc++.h>
using namespace std;
int n;
int A[15];
int dir[15];

void print()
{
    for(int i=1;i<n;i++)
        printf("%d ",A[i]);
    printf("%d\n",A[n]);
}
bool IF_Active(int i) //判断是否活跃（前面的数字比它小就是活跃）
{
    if(i+dir[i]<=0||i+dir[i]>n)
        return false;
    if(A[i+dir[i]]<A[i])
        return true;
    return false;
}

int MAX_Active() //找到最大的活跃数字
{
    int id=n+1;
    for(int i=1;i<=n;i++)
    {
        if(IF_Active(i)&&A[id]<A[i])
            id=i;
    }
    return id;
}
int Swap(int i) //交换最大的活跃数字和它前面的那个数字，注意方向也要交换
{
    int c=A[i];
    A[i]=A[i+dir[i]];
    A[i+dir[i]]=c;

    c=dir[i];
    dir[i]=dir[i+c];
    dir[i+c]=c;

    return i+c;
}
void UPdate(int index)
{
    for(int i=1;i<=n;i++)
    {
        if(A[index]<A[i])
            dir[i]=-dir[i];
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        A[i]=i;
        dir[i]=-1;
    }
    print();
    
    while(1)
    {
        int id=MAX_Active();
        if(id==n+1) break;
        id=Swap(id);
        UPdate(id);
        print();
    }
    return 0;
}