生成{1,2,...,n}的排列的算法-组合数学

逃离我推掉我的手 2022-07-16 09:00 212阅读 0赞

生成\{1,2,...,n\}的排列的算法

## 步骤： ##

①求出最大的可移动整数m；

②交换m和它的箭头所指向的与它相邻的数；

③交换所有满足p>m的整数p上的箭头方向。

##    Note： ##

箭头：给定一个整数，我们给它一个方向，即在整数的上方画一个向左或是向右的箭头。初始化情况下，默认有序递增的所有数的箭头方向向左。

可移动整数：如果一个整数k的箭头指向一个与其相邻但比其小的整数，则称这个整数是可移动的。

Ps：

这是关于《组合数学》课上的内容我写的的一个小程序…丑陋的代码…诶 :-(

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    #define INF 0x3f3f3f3f
    #define maxn 10000
    int n;
    struct Number
    {
        bool dir;//方向，左0右1
        int pos;//下标位置从1~n编号
        int no;//数值
    } num[maxn];
    void Init()//初始化
    {
        for(int i=1; i<=n; ++i)
        {
            num[i].dir=0;
            num[i].pos=num[i].no=i;
        }
    }
    int Find_Pos2Num(int p)//寻找对应方向上的位置是什么数
    {
        for(int i=1; i<=n; ++i)
            if(num[i].pos==p)//顺序查找出一致位置
                return num[i].no;//返回该位置上的数
        return -1;
    }
    int Find_Num2Pos(int m)//寻找数的下标i的值
    {
        for(int i=1; i<=n; ++i)
            if(num[i].no==m)//顺序查找出一致位置
                return i;//返回该位置上的数
        return -1;
    }
    int MaxM()//①求出最大的可移动整数m
    {
        int p,i,m=n;//设置m是为了保证n的始终不变性
        while(i>0)
        {
            i=Find_Num2Pos(m);//从大到小遍历，找到数值对应的下标位置
            --m;
            if(num[i].dir==0)//左边
            {
                p=Find_Pos2Num(num[i].pos-1);
                if(p!=-1)//查找成功
                    if(p<num[i].no)
                        return num[i].no;//最大可移动整数
            }
            else if(num[i].dir==1)//右边
            {
                p=Find_Pos2Num(num[i].pos+1);
                if(p!=-1)//查找成功
                    if(p<num[i].no)
                        return num[i].no;//最大可移动整数
            }
        }
        return -1;
    }
    void Shift(int m)//②交换m和它的箭头所指向的与它相邻的数
    {
        int i;
        i=Find_Num2Pos(m);//找到m所在的下标位置
        if(num[i].dir==0)//与左边交换，pos始终不变
        {
            swap(num[i].no,num[i-1].no);
            swap(num[i].dir,num[i-1].dir);
        }
        else if(num[i].dir==1)//与右边交换，pos始终不变
        {
            swap(num[i].no,num[i+1].no);
            swap(num[i].dir,num[i+1].dir);
        }
    }
    void ChangeDir(int m)//③交换所有满足p>m的整数p上的箭头方向
    {
        for(int i=1; i<=n; ++i)
            if(num[i].no>m)
                num[i].dir=!num[i].dir;
    }
    void Out()//输出当前的排列情况
    {
        for(int i=1; i<=n; ++i)
            cout<<num[i].no<<"("<<(num[i].dir==0?"←":"→")<<") ";
        cout<<endl;
    }
    int main()
    {
        cin>>n;
        Init();
        Out();
        int m=MaxM();
        while(m!=-1)
        {
            Shift(m);
            ChangeDir(m);
            Out();
            m=MaxM();
        }
        return 0;
    }

![20161013170912051][]

[20161013170912051]: /images/20220716/f44463dcb9ba4967a5dd81f7b111395a.png