按字典序生成{1,2,...,n}的r子集的算法-组合数学

浅浅的花香味﹌ 2022-07-16 09:43 219阅读 0赞

按字典序生成\{1,2,...,n\}的r子集的算法

算法步骤：

从r子集a\[1\]a\[2\]...a\[r\]=12...r开始。

当a\[1\]a\[2\]...a\[r\]!=(n-r+1)(n-r+2)...n时，执行下列操作：

①确定最大的整数k，使得a\[k\]+1<=n且a\[k\]+1不是a\[1\],a\[2\],...,a\[r\]中的一个；

②用r子集a\[1\]...a\[k-1\](a\[k\]+1)(a\[k\]+2)...(a\[k\]+r-k+1)替换a\[1\]a\[2\]...a\[r\]。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    #define INF 0x3f3f3f3f
    #define maxn 10000
    int n,r;
    int a[maxn];
    
    void Init()//初始化
    {
        for(int i=1; i<=r; ++i)
            a[i]=i;
    }
    bool Check()//检查a[1]a[2]...a[r]!=(n-r+1)(n-r+2)...n
    {
        int j=1;
        for(int i=1; i<=r; ++i)
        {
            if(a[i]!=n-r+j)
                return false;
            ++j;
        }
        return true;
    }
    bool Contain(int k)//判断a[k]+1是否为a[1],a[2],...,a[r]中的一个
    {
        for(int i=1; i<=r; ++i)
            if(k==a[i])
                return false;
        return true;
    }
    int Findk()//确定最大的整数k，使得a[k]+1<=n且a[k]+1不是a[1],a[2],...,a[r]中的一个
    {
        int Max=-1,temp=-1;
        for(int i=1; i<=r; ++i)
            if(a[i]+1<=n&&Contain(a[i]+1))
                if(Max<a[i])
                {
                    Max=a[i];
                    temp=i;
                }
        return temp;
    }
    void Change(int k)//用r子集a[1]...a[k-1](a[k]+1)(a[k]+2)...(a[k]+r-k+1)替换a[1]a[2]...a[r]
    {
        int j=1,t=a[k];
        for(int i=k; i<=r; ++i)
        {
            a[i]=t+j;
            ++j;
            if(j>r-k+1) break;
        }
    }
    void Out()//输出当前的排列情况
    {
        for(int i=1; i<=r; ++i)
            cout<<a[i];
        cout<<endl;
    }
    int main()
    {
        cin>>n>>r;
        Init();
        Out();
        while(!Check())
        {
            Change(Findk());
            Out();
            //system("pause");
        }
        return 0;
    }

![20161013194341277][]

[20161013194341277]: /images/20220716/635483156efb41459cfe9941ab0a5558.png