The following extremely straightforward C program can perhaps provide some insight into how these sequences are constructed. It first constructs the graph $G$ on $2^n$ vertices (the pattern is $n$ bits wide) of all possible patterns with a forward edge between two vertices $u$ and $v$ if the lower $n-1$ bits of $u$ match the upper $n-1$ bits of $v.$ Next the program builds Hamiltonian paths of $G$ and whenever it finds one, the sequence of nodes and of bits is displayed. Not difficult to adapt to different pattern sizes and alphabets. Compile with GCC and run from the command line with a single argument ($n$).
#include #include typedef struct{ unsigned int nb0, nb1; } adjpair; void backtrack(unsigned int n, unsigned int count, unsigned int *path, unsigned char *marks, adjpair *nbs, unsigned int pos) { unsigned int m; if(pos==count-1){ for(m=0; m>(n-1))>0 ? '1' : '0'); } printf("\n"); return; } unsigned int cur = path[pos]; if(!(marks[nbs[cur].nb0])){ path[pos+1] = nbs[cur].nb0; marks[nbs[cur].nb0] = 1; backtrack(n, count, path, marks, nbs, pos+1); marks[nbs[cur].nb0] = 0; } if(!(marks[nbs[cur].nb1])){ path[pos+1] = nbs[cur].nb1; marks[nbs[cur].nb1] = 1; backtrack(n, count, path, marks, nbs, pos+1); marks[nbs[cur].nb1] = 0; } } int main(int argc, char **argv){ unsigned int n; if(argc!=2 || sscanf(argv[1], "%u", &n)!=1 || n<1 || n>=256){ fprintf(stderr, "positive integer expected\n"); exit(-1); } unsigned int count = 1<