C++ 格雷码位置变化序列 Gray Code
格雷码
数据结构、算法与应用 第一张练习 26
两个代码之间的 海明距离 (Hamming distance) 是对应位不等的数量。 例如：100和010的海明距离是2。 一个（二进制）格雷码是一个代码序列，其中任意相邻的两个代码之间的海明距离是1。 子集生成的序列 000，100，010，001...111 不是格雷码，因为100，010海明距离是2。 而三位代码序列 000，100，110，010，011，111，101，001是格雷码。
在代码序列的一些应用中，从一个代码到下一个代码的代价取决于它们的海明距离。因此我们希望这个代码序列是格雷码。格雷码可以用代码变化的位置序列简洁地表示。 对于上面的格雷码，位置序列是1，2，1，3，1，2，1.
令g(n)是一个n元素的格雷码的位置变化序列。以下是g的递归定义：
1 n=1
g(n-1),n,g(n-1) n>1注意这个是位置变化序列，并不是格雷码生成。
以下为算法
递归版：
#include <iostream>
#include <cmath>
/*
* 格雷码序列数量是 2^n，相应的变化序列数量是 2^n - 1
*/
int * GrayCodeChangeSequence( int n ){
int len = pow(2,n)-1;
int * arr = new int[len];
if( n<2 ){ arr[0]=1; return arr; }
int half = (len-1)>>1;
int * half_arr = GrayCodeChangeSequence( n-1 );
for( int i=0; i<half; i ++ ){
arr[i] = half_arr[i];
}
arr[half] = n;
for( int i=0; i<half; i ++ ){
arr[i+half+1] = half_arr[i];
}
return arr;
}
void testGCCS( int n ){
int * b = GrayCodeChangeSequence(n);
for( int i = 0; i< pow(2,n)-1 ; i++ ){
std::cout << b[i] << ' ';
}
std::cout << endl;
delete[] b;
}
int main()
{
testGCCS(1);
testGCCS(2);
testGCCS(3);
testGCCS(4);
testGCCS(5);
}
测试分别输出：
1
1 2 1
1 2 1 3 1 2 1
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1优化
实际上格雷码修改序列生成和斐波那契数列的生成效率是需要进一步优化的，原因在于每一次收到递归结果，都需要遍历一次结果并且覆盖到当前的序列中。从渐进意义上来说，复杂度是O(n2) 而且相对于序列的长度增长渐进意义上远大于n，这个时候如果能够在一次遍历的情况下配合少量计算那么可以将复杂度降低至O(n)
在迭代之前先观察test方法输出的序列特点，其实我们可以看到 当n>1时，除了n其他的元素都是在不断的重复先前已有的序列，这样我们就能够通过一个游标来模拟逆向递归的过程，反复的读取已有的元素。并填入到后续中。
迭代版
#include <iostream>
#include <cmath>
using namespace std;
/*
* GCCS.h
* 格雷码序列数量是 2^n，相应的变化序列数量是 2^n - 1
*/
int * GrayCodeChangeSequence( int n ){
int length = std::pow(2,n)-1;
int * arr = new int[length];
arr[0] = 1;
if( n<2 ){ return arr; }
int cursor = 2;
while( cursor < n+1 ){
int len = pow(2,cursor)-1;
int half = (len-1)>>1;
/*
* 请注意，此时half左侧已经填写过，没有必要再填写
*/
arr[half] = cursor; // 第一次编译错误 cursor写成了n。模拟递归每一次的中点是cursor，而不是最终的n。
for( int i=0; i<half; i++ ){
arr[i+half+1] = arr[i];
}
cursor++;
}
return arr;
}
void testGCCS( int n ){
int * b = GrayCodeChangeSequence(n);
for( int i = 0; i< std::pow(2,n)-1 ; i++ ){
std::cout << b[i] << ' ';
}
std::cout << endl;
}
int main()
{
testGCCS(1);
testGCCS(2);
testGCCS(3);
testGCCS(4);
testGCCS(5);
}
输出与迭代版一致。
扩展 通过位置变化序列 生成格雷码序列
实际上通过位置变化序列来进行格雷码生成是十分容易的。 位置变化序列中的数字是几，我们就将对应的数字-1得到元素的秩(Rank)，并将其取反即可。 那么 2^n-1 次位置变化，刚好得出 2^n 个格雷码代码单元。 格雷码从n个0开始，依次变化。
/*
* 通过格雷码变换序列返回格雷码序列，总项数为2^n
*/
#include <iostream>
#include <cmath>
#include "GCCS.h";
void copyGCS( char* n_gccs, char* o_gccs, int n ){
for( int i=0; i<n; i++ ){
n_gccs[i] = o_gccs[i];
}
}
char** GCCSToGCS( int * gccs, int n ){
int len = pow(2,n);
char** codeSequence = new char*[len];
codeSequence[0] = new char[n];
for( int i=0;i<n;i++ ){
codeSequence[0][i] = '0';
}
for(int i=0;i<len-1;i++){ // 遍历gccs 位置变化序列
codeSequence[i+1] = new char[n];
copyGCS( codeSequence[i+1], codeSequence[i], n ); // 深拷贝
codeSequence[i+1][ gccs[i]-1 ] = codeSequence[i+1][ gccs[i]-1 ]=='1'?'0':'1' ; // 字符取反
}
return codeSequence;
}
void outChars( char* s, int n ){
for(int i=0;i<n;i++){
cout << s[i];
}
cout << ' ';
}
void testGCS( int n ){
int* gccs = GrayCodeChangeSequence(n);
char** gcs = GCCSToGCS( gccs, n );
int len = pow(2,n);
for( int i=0; i< len; i++){
outChars( gcs[i],n );
}
cout << endl;
}
int main()
{
testGCS(1);
testGCS(2);
testGCS(3);
testGCS(4);
testGCS(5);
}
测试会输出:
0 1
00 10 11 01
000 100 110 010 011 111 101 001
0000 1000 1100 0100 0110 1110 1010 0010 0011 1011 1111 0111 0101 1101 1001 0001
00000 10000 11000 01000 01100 11100 10100 00100 00110 10110 11110 01110 01010 11010 10010 00010 00011 10011 11011 01011 01111 11111 10111 00111 00101 10101 11101 01101 01001 11001 10001 00001
文章地址: C++ 格雷码位置变化序列 Gray Code - Sprite keep learning
最近回复