以反射Gray码的顺序生成0,1的n元组的算法-组合数学

亦凉 2022-07-16 09:28 145阅读 0赞

以反射Gray码的顺序生成0,1的n元组的算法

算法步骤如下：

从n元组a\[n-1\]a\[n-2\]...a\[0\]=00...0开始；

当a\[n-1\]a\[n-2\]...a\[0\]!=00...0时，执行下面操作：  
①计算sum=a\[n-1\]+a\[n-2\]+...+a\[0\]；

②如果sum是偶数，则改变a\[0\]（从0变到1或是从1变到0）；

③否则，确定这样的j，使得a\[j\]=1且满足j>i的所有i有a\[i\]=0（即这是从左边开始第一个1），然后，改变a\[j+1\]（从0变到1或是从1变到0）。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <cmath>
    #include <bitset>
    #include <algorithm>
    using namespace std;
    #define INF 0x3f3f3f3f
    #define maxn 10010
    int a[maxn];
    int n;
    
    void Init()
    {
        memset(a,0,sizeof(a));
    }
    bool Check()//检查是否a[n-1]==1且其它全为0
    {
        if(a[n-1]!=1) return false;
        for(int i=0; i<n-1; ++i)
            if(a[i]!=0) return false;
        return true;
    }
    int Sum()//数组a所有元素之和
    {
        int sum=0;
        for(int i=0; i<n; ++i)
            sum+=a[i];
        return sum;
    }
    void Change()//取反第一个1之前一位的数值
    {
        for(int i=0; i<n; ++i)
            if(a[i]==1)
            {
                a[i+1]=!a[i+1];
                break;
            }
    }
    void Out()//输出数组a
    {
        for(int i=n-1; i>=0; --i)
            cout<<a[i]<<" ";
        cout<<endl;
    }
    int main()
    {
        cin>>n;
        Init();//初始化全部置零
        while(!Check())
        {
            Out();//输出数组a
            if(Sum()%2==0)//若所有元素之和为偶数
                a[0]=!a[0];//取反a[0]
            else if(Sum()%2==1)//若所有元素之和为奇数
                Change();//取反第一个1之前一位的数值
        }
        Out();//输出数组a
        return 0;
    }

![20161013170614550][]

[20161013170614550]: /images/20220716/d21132175d0b4773a9ba87267845446c.png