How to find equidistant hamming sequences?

[fra93]

Given N as the number of bits, how to find N sequences of (2^N/N) numbers each such that: given an arbitrary number n, there is always one number in each sequence that has hamming distance 1 from n.

As a reference hamming distance 1 means that two numbers have only one bit that is different.

For example given N=4, one of the possible solution to the aforementioned problem is:

s0 = [ 0000 0001 1110 1111 ]
s1 = [ 0010 0101 1101 1010 ]
s2 = [ 0100 0011 1011 1100 ]
s3 = [ 1000 0110 1001 0111 ]

If we consider for example s3 we always find a number that has hamming distance 1 from a complete sequence of numbers.

complete sequence : 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
relative s3 numbers : 1000 1001 0110 0111 0110 0111 0111 0111 1000 1001 1000 1001 1000 1001 0110 0111

I apologize in advance for posting the same question in another purely math forum with the same title.
I am re-posting my question here because I believe this forum might approach the answer from a more algorithmic point of view. Hopefully this is the appropriate place for this discussion.

So far I have been able to calculate those codes with N = 8 using a graph coloring algorithm, which does not scale well with the number of bits.

I am looking for an algorithm which has at most O(n^3) as time complexity, or a formula to calculate directly the sequences.

For N=8, one of the possible solutions is provided in the code below.
I wrote the code so anybody can easily test their idea, and it should work as long as you do not accept the challenge.

If C is a hard for anybody I could rewrite the code in Python or Octave.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
 
#define ACCEPT_CHALLENGE 0
 
#if ACCEPT_CHALLENGE == 0
 
#define M 32        // the numbers in each base
#define N 256      // the numbers in a complete sequence
#define LOGN 8   // the number of bases
 
#else
 
#define M 4096
#define N 65536
#define LOGN 16
 
#endif 
 
void printbin( int a, int len ){
   if ( a != -1 ){
       for ( int i =1; i <= len ; i++ ){
           printf("%d",(a>>(len-i)&1));
       }
   } else {
       for ( int i =1; i <= len ; i++ ){
           printf(" ");
       }
   }
}
 
int to_grey(int a ){
    a = ( a >> 1 ) ^ a ;
    return a;
}
 
int count_ones( int a , int len ){
 
   int ones;
 
   ones = 0;
   for ( int i =1; i <= len ; i++ ){
       ones += (a>>(len-i)&1) ;
   }
 
   return ones;
}
 
 
void generate_bases( int ** bases ){
 
    bases[0][0]  =   0; bases[1][0]  =   1; bases[2][0]  =   2; bases[3][0]  =   3;
    bases[0][1]  =   7; bases[1][1]  =   6; bases[2][1]  =   5; bases[3][1]  =   4;
    bases[0][2]  =  25; bases[1][2]  =  24; bases[2][2]  =  27; bases[3][2]  =  26;
    bases[0][3]  =  30; bases[1][3]  =  31; bases[2][3]  =  28; bases[3][3]  =  29;
    bases[0][4]  =  42; bases[1][4]  =  43; bases[2][4]  =  40; bases[3][4]  =  41;
    bases[0][5]  =  45; bases[1][5]  =  44; bases[2][5]  =  47; bases[3][5]  =  46; 
    bases[0][6]  =  51; bases[1][6]  =  50; bases[2][6]  =  49; bases[3][6]  =  48;
    bases[0][7]  =  52; bases[1][7]  =  53; bases[2][7]  =  54; bases[3][7]  =  55;
    bases[0][8]  =  75; bases[1][8]  =  74; bases[2][8]  =  73; bases[3][8]  =  72;
    bases[0][9]  =  76; bases[1][9]  =  77; bases[2][9]  =  78; bases[3][9]  =  79;
    bases[0][10] =  82; bases[1][10] =  83; bases[2][10] =  80; bases[3][10] =  81;
    bases[0][11] =  85; bases[1][11] =  84; bases[2][11] =  87; bases[3][11] =  86;
    bases[0][12] =  97; bases[1][12] =  96; bases[2][12] =  99; bases[3][12] =  98;
    bases[0][13] = 102; bases[1][13] = 103; bases[2][13] = 100; bases[3][13] = 101;
    bases[0][14] = 120; bases[1][14] = 121; bases[2][14] = 122; bases[3][14] = 123;
    bases[0][15] = 127; bases[1][15] = 126; bases[2][15] = 125; bases[3][15] = 124;
    bases[0][16] = 255; bases[1][16] = 254; bases[2][16] = 253; bases[3][16] = 252;
    bases[0][17] = 248; bases[1][17] = 249; bases[2][17] = 250; bases[3][17] = 251;
    bases[0][18] = 230; bases[1][18] = 231; bases[2][18] = 228; bases[3][18] = 229;
    bases[0][19] = 225; bases[1][19] = 224; bases[2][19] = 227; bases[3][19] = 226;
    bases[0][20] = 213; bases[1][20] = 212; bases[2][20] = 215; bases[3][20] = 214;
    bases[0][21] = 210; bases[1][21] = 211; bases[2][21] = 208; bases[3][21] = 209;
    bases[0][22] = 204; bases[1][22] = 205; bases[2][22] = 206; bases[3][22] = 207;
    bases[0][23] = 203; bases[1][23] = 202; bases[2][23] = 201; bases[3][23] = 200;
    bases[0][24] = 180; bases[1][24] = 181; bases[2][24] = 182; bases[3][24] = 183;
    bases[0][25] = 179; bases[1][25] = 178; bases[2][25] = 177; bases[3][25] = 176;
    bases[0][26] = 173; bases[1][26] = 172; bases[2][26] = 175; bases[3][26] = 174;
    bases[0][27] = 170; bases[1][27] = 171; bases[2][27] = 168; bases[3][27] = 169;
    bases[0][28] = 158; bases[1][28] = 159; bases[2][28] = 156; bases[3][28] = 157;
    bases[0][29] = 153; bases[1][29] = 152; bases[2][29] = 155; bases[3][29] = 154;
    bases[0][30] = 135; bases[1][30] = 134; bases[2][30] = 133; bases[3][30] = 132;
    bases[0][31] = 128; bases[1][31] = 129; bases[2][31] = 130; bases[3][31] = 131;
 
    bases[4][0]  =   8; bases[5][0]  =   9; bases[6][0]  =  10; bases[7][0]  =  11;
    bases[4][1]  =  15; bases[5][1]  =  14; bases[6][1]  =  13; bases[7][1]  =  12;
    bases[4][2]  =  17; bases[5][2]  =  16; bases[6][2]  =  19; bases[7][2]  =  18;
    bases[4][3]  =  22; bases[5][3]  =  23; bases[6][3]  =  20; bases[7][3]  =  21;
    bases[4][4]  =  34; bases[5][4]  =  35; bases[6][4]  =  32; bases[7][4]  =  33;
    bases[4][5]  =  37; bases[5][5]  =  36; bases[6][5]  =  39; bases[7][5]  =  38;
    bases[4][6]  =  59; bases[5][6]  =  58; bases[6][6]  =  57; bases[7][6]  =  56;
    bases[4][7]  =  60; bases[5][7]  =  61; bases[6][7]  =  62; bases[7][7]  =  63;
    bases[4][8]  =  67; bases[5][8]  =  66; bases[6][8]  =  65; bases[7][8]  =  64;
    bases[4][9]  =  68; bases[5][9]  =  69; bases[6][9]  =  70; bases[7][9]  =  71;
    bases[4][10] =  90; bases[5][10] =  91; bases[6][10] =  88; bases[7][10] =  89;
    bases[4][11] =  93; bases[5][11] =  92; bases[6][11] =  95; bases[7][11] =  94;
    bases[4][12] = 105; bases[5][12] = 104; bases[6][12] = 107; bases[7][12] = 106;   
    bases[4][13] = 110; bases[5][13] = 111; bases[6][13] = 108; bases[7][13] = 109;
    bases[4][14] = 112; bases[5][14] = 113; bases[6][14] = 114; bases[7][14] = 115;
    bases[4][15] = 119; bases[5][15] = 118; bases[6][15] = 117; bases[7][15] = 116;
    bases[4][16] = 247; bases[5][16] = 246; bases[6][16] = 245; bases[7][16] = 244;
    bases[4][17] = 240; bases[5][17] = 241; bases[6][17] = 242; bases[7][17] = 243;
    bases[4][18] = 238; bases[5][18] = 239; bases[6][18] = 236; bases[7][18] = 237;
    bases[4][19] = 233; bases[5][19] = 232; bases[6][19] = 235; bases[7][19] = 234;
    bases[4][20] = 221; bases[5][20] = 220; bases[6][20] = 223; bases[7][20] = 222;
    bases[4][21] = 218; bases[5][21] = 219; bases[6][21] = 216; bases[7][21] = 217;
    bases[4][22] = 196; bases[5][22] = 197; bases[6][22] = 198; bases[7][22] = 199;
    bases[4][23] = 195; bases[5][23] = 194; bases[6][23] = 193; bases[7][23] = 192;
    bases[4][24] = 188; bases[5][24] = 189; bases[6][24] = 190; bases[7][24] = 191;
    bases[4][25] = 187; bases[5][25] = 186; bases[6][25] = 185; bases[7][25] = 184;
    bases[4][26] = 165; bases[5][26] = 164; bases[6][26] = 167; bases[7][26] = 166;
    bases[4][27] = 162; bases[5][27] = 163; bases[6][27] = 160; bases[7][27] = 161;
    bases[4][28] = 150; bases[5][28] = 151; bases[6][28] = 148; bases[7][28] = 149;
    bases[4][29] = 145; bases[5][29] = 144; bases[6][29] = 147; bases[7][29] = 146;
    bases[4][30] = 143; bases[5][30] = 142; bases[6][30] = 141; bases[7][30] = 140;
    bases[4][31] = 136; bases[5][31] = 137; bases[6][31] = 138; bases[7][31] = 139;  
 
    return;
 
}
 
 
int main(){
 
   int i, j, k ;
   int basei, basej, one_cnt, error, occurrance;
   int ** bases;
 
   bases = (int **) malloc(LOGN*sizeof(int *));
   for ( i = 0 ; i < LOGN ; i++ ) bases[i] = (int *) malloc(M*sizeof(int));
 
   // your soulution here
   generate_bases( bases );
 
   //check hamming distance
   error = 0;
   for ( basei = 0; (basei < LOGN) && (!error); basei++ ){
 
       printf("checking base %4d\n",basei);
 
       for ( k = 0; (k < N) && (!error); k++ ){
           error = 1;
           for ( basej = 0; basej < M; basej++ ){
               one_cnt = count_ones( k ^ bases[basei][basej], LOGN);
               if (( one_cnt == 0 )||( one_cnt == 1 )){
                    error = 0;
               }
           }
           if ( error == 1 ){
               printf("error in base %4d, counter example %4d ",basei,k);
               printbin(k,LOGN);
               printf("\n");
 
               // print base
               for ( i = basei; i == basei ; i++ ){
                   for ( j = 0; j < M ; j++ ){
                       printbin(bases[i][j],LOGN);
                       printf(" ");
                   }
                   printf("\n");
               }
               printf("\n");
           }
       }
   }
 
   //check unicity
   for ( i = 0; (i < N) && ( ! error ); i++ ){
       occurrance = 0;
       for ( basei = 0; (basei < LOGN) && (!error); basei++ ){
           for ( basej = 0; basej < M; basej++ ){
               if ( bases[basei][basej] == i ){
                   occurrance ++;
               }
           }
        }
        if ( occurrance != 1 ){
             error = 1;
        }
   }
 
   if ( error == 0 ){
       // print bases
       printf("\n\nvalid bases:\n");
       for ( i = 0; i < LOGN ; i++ ){
           for ( j = 0; j < M ; j++ ){
                printf("%4d, ",bases[i][j]);
                //printbin(bases[i][j],LOGN);
                printf(" ");
                if ( j == M/2-1){
                    printf("\n");
                }
           }
           printf("\n\n");
       }
       printf("\n");
   } else {
       printf("not valid bases\n");
   }
 
   for ( i = 0 ; i < LOGN ; i++ ) free(bases[i]) ;
   free(bases);
 
   return 0;
 
}
 

[dayamafor]

i also had same question