define

A set of MMM base NNN bit gray codes is an ordered, non-repetitive set of MMM base NNN bits. So there’s MMM to the NNN power in this set. There is one and only one difference between two numbers. The first and last numbers in this set are also considered adjacent.

The input

A row of NNN and MMM represent gray code bits and base, where 2≤ N ≤12,2≤m≤10, Mn ≤50000002\le n\ LE 12,2 \ LE m \le 10, M ^ N \ LE 50000002≤ N ≤12,2≤ M ≤10,mn≤5000000

The output

Any gray code coding scheme, each code line, two adjacent lines of gray code difference one, the first line and the last line are also considered adjacent.

The sample

The input

2, 3,Copy the code

The output

00
01
02
12
10
11
21
22
20
Copy the code

Generation algorithm

The encoding result of NNN bit MMM base gray code is stored in string array SSS, and the length of string array is Lenlenlen when the length of KKK bit is constructed

  1. Initialize k=1,len=mk=1,len=mk=1,len=m, first construct KKK bit MMM grey string array, insert 0 ~ (m−1)0\sim (m-1)0 ~ (m−1) into array SSS, such as 111 bit 333: 0,1,20,1,20,1,2
  2. Structure of k + 1 k + 1, k + 1 first copies the coding results of KKK bit into MMM times in array, such as: 0-0,1,2,0,1,2,0,1,20,1,2 \ to0, 1,2,0,1,2,0,1,20,1,2 – > 0,1,2,0,1,2,0,1,2
  3. For KKK bit encoding, len= Mn − 1Len = M ^{n-1}len= MN −1, the expanded array is divided into Lenlenlen group in order, such as 111-bit 333 base: ,1,2,0,1,2,0,1,2 – > 0 (0), (0), (0, 0,1,2,0,1,2,0,1,2 \ to (0), (0), (0, 0,1,2,0,1,2,0,1,2 – (0), (0), ( 0,1,2), group iii circulates right position iii (counting starts from 000) : (0), (0), (0) and (0), (2, 1), (1, 0) (0), (0), (0) \ the to (0), (2, 1), (1, 0) (0), (0), (0) and (0), (2, 1), (1, 0)
  4. For group III, insert the number III before each element to form the coding result of NNN bit MMM base gray code, as follows: (00,01,02), (12, 11), (21,22,20) (00,01,02), (12, 11), (21,22,20) (00,01,02), (12, 11), (21,22,20)
  5. Update k=k+1,len=len∗mk=k+1,len=len*mk=k+1,len=len∗m, and repeat step 222 until k=nk=nk=n

Back in the implementation

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string code[50001];// Encode the result
int n,m;
int len;
void dfs(int k){
	if(k==n+1) {// The search is over
		return;
	}
	for(inti=len; i<m*len; i++){// Copy to loop right
		code[i]=code[(i-i/len+len)%len];
	}
	for(int i=0; i<m*len; i++){// Insert the I prefix into the I group
		code[i]=char('0'+(i/len%m))+code[i];
	}
	len*=m;// Update the length
	dfs(k+1);
}
int main(a){
	cin>>n>>m;
	len=1;// The multiplication cannot start with 0
	dfs(1);// Start the search at 1
	for(int i=0; i<len; i++){ cout<<code[i]<<endl;// Output the result
	}
	return 0;
}
Copy the code

Cycle to achieve

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string code[50001];// Encode the result
int n,m,k,len;
int main(a){
	cin>>n>>m;
	len=1;// The multiplication cannot start with 0
	k=1;
	while(k<=n){
		for(intj=len; j<m*len; j++){// Copy to loop right
			code[j]=code[(j-j/len+len)%len];
		}
		for(int i=0; i<m*len; i++){// Insert the I prefix into the I group
			code[i]=char('0'+(i/len%m))+code[i];
		}
		len*=m;// Update the length
		k++;
	}
	for(int i=0; i<len; i++){ cout<<code[i]<<endl;// Output the result
	}
	return 0;
}
Copy the code