【C++】扩展格雷码生成算法

一组 m m m进制的 n n n位格雷码，是一组有序的、无重复的、 m m m进制 n n n位数。这组数中一共有 m m m的 n n n次方个数。相邻的（因有序，所以有相邻的概念）两个数之间有且只有一位是不同的。这组数的第一个和最后一个数，也被视为相邻的数。

一行 n n n和 m m m，分别表示格雷码位数和进制，其中 2 ≤ n ≤ 12 , 2 ≤ m ≤ 10 , m n ≤ 5000000 2le nle 12, 2le m le 10, m^nle 5000000 2≤n≤12,2≤m≤10,mn≤5000000

任意一种格雷码编码方案，每个编码一行，相邻两行格雷码相差一位，第一行和最后一行也算相邻。

输入

2 3

输出

00
01
02
12
10
11
21
22
20

算法思想
设 n n n位 m m m进制格雷码的编码结果存储于字符串数组 s s s，构造 k k k位长度时字符串数组长度为 l e n len len

1. 初始化 k = 1 , l e n = m k=1,len=m k=1,len=m，首先构造 k k k位 m m m进制格雷码的字符串数组，将 0 ∼ ( m − 1 ) 0sim (m-1) 0∼(m−1)依次插入数组 s s s，如 1 1 1位 3 3 3进制： 0 , 1 , 2 0,1,2 0,1,2
2. 构造 k + 1 k+1 k+1位编码，首先将 k k k位的编码结果复制成 m m m倍存于数组中，如： 0 , 1 , 2 → 0 , 1 , 2 , 0 , 1 , 2 , 0 , 1 , 2 0,1,2to0,1,2,0,1,2,0,1,2 0,1,2→0,1,2,0,1,2,0,1,2
3. 对于 k k k位编码，长度为 l e n = m n − 1 len=m^{n-1} len=mn−1，将扩充后的数组按顺序分为 l e n len len组，如 1 1 1位 3 3 3进制： 0 , 1 , 2 , 0 , 1 , 2 , 0 , 1 , 2 → ( 0 , 1 , 2 ) , ( 0 , 1 , 2 ) , ( 0 , 1 , 2 ) 0,1,2,0,1,2,0,1,2to(0,1,2),(0,1,2),(0,1,2) 0,1,2,0,1,2,0,1,2→(0,1,2),(0,1,2),(0,1,2)，第 i i i组循环右移 i i i位(计数从 0 0 0开始)： ( 0 , 1 , 2 ) , ( 0 , 1 , 2 ) , ( 0 , 1 , 2 ) → ( 0 , 1 , 2 ) , ( 2 , 0 , 1 ) , ( 1 , 2 , 0 ) (0,1,2),(0,1,2),(0,1,2)to (0,1,2),(2,0,1),(1,2,0) (0,1,2),(0,1,2),(0,1,2)→(0,1,2),(2,0,1),(1,2,0)
4. 对于第 i i i组，在每个元素前插入数字 i i i，构成 n n n位 m m m进制格雷码的编码结果，如： ( 00 , 01 , 02 ) , ( 12 , 10 , 11 ) , ( 21 , 22 , 20 ) (00,01,02),(12,10,11),(21,22,20) (00,01,02),(12,10,11),(21,22,20)
5. 更新 k = k + 1 , l e n = l e n ∗ m k=k+1,len=len*m k=k+1,len=len∗m，重复第 2 2 2步直到 k = n k=n k=n

#include 
#include 
#include 
using namespace std;
string code[50001];//编码结果 
int n,m;
int len;
void dfs(int k){
	if(k==n+1){//搜索结束 
		return;
	}
	for(int i=len;i>n>>m;
	len=1;//乘法不能用0作为初始值 
	dfs(1);//从1开始搜索 
	for(int i=0;i 
循环实现 
#include 
#include 
#include 
using namespace std;
string code[50001];//编码结果 
int n,m,k,len;
int main(){
	cin>>n>>m;
	len=1;//乘法不能用0作为初始值
	k=1;
	while(k<=n){
		for(int j=len;j