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 0111 1000 1111 ]
s1 = [ 0001 0110 1001 1110 ]
s2 = [ 0010 0101 1010 1101 ]
s3 = [ 0011 0100 1011 1100 ]
If we consider for example s2 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 s2 numbers : 0010 0101 0010 0010 0101 0101 0010 0101 1010 1101 1010 1010 1101 1101 1010 1101
For N=8, one of the possible solution is as below (with decimal numbers).
s0 = [ 0 7 25 30 42 45 51 52 75 76 82 85 97 102 120 127 255 248 230 225 213 210 204 203 180 179 173 170 158 153 135 128 ]
s1 = [ 1 6 24 31 43 44 50 53 74 77 83 84 96 103 121 126 254 249 231 224 212 211 205 202 181 178 172 171 159 152 134 129 ]
s2 = [ 2 5 27 28 40 47 49 54 73 78 80 87 99 100 122 125 253 250 228 227 215 208 206 201 182 177 175 168 156 155 133 130 ]
s3 = [ 3 4 26 29 41 46 48 55 72 79 81 86 98 101 123 124 252 251 229 226 214 209 207 200 183 176 174 169 157 154 132 131 ]
s4 = [ 8 15 17 22 34 37 59 60 67 68 90 93 105 110 112 119 247 240 238 233 221 218 196 195 188 187 165 162 150 145 143 136 ]
s5 = [ 9 14 16 23 35 36 58 61 66 69 91 92 104 111 113 118 246 241 239 232 220 219 197 194 189 186 164 163 151 144 142 137 ]
s6 = [ 10 13 19 20 32 39 57 62 65 70 88 95 107 108 114 117 245 242 236 235 223 216 198 193 190 185 167 160 148 147 141 138 ]
s7 = [ 11 12 18 21 33 38 56 63 64 71 89 94 106 109 115 116 244 243 237 234 222 217 199 192 191 184 166 161 149 146 140 139 ]
The codes shown above have been calculated 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.
We know that $N$ must be a power of $2$ so assume this.
The Hamming code Wikipedia is a perfect code with length $2^m-1,$ dimension $2^m-m-1,$ and minimum distance $d=3.$ Since $d=2t+1,$ this means spheres of radius $t=1$ around Hamming codewords are disjoint and every vector in $\{0,1\}^{2^m-1}$ is either a codeword or is at distance $1$ from a codeword. The number of codewords is $M=2^{2^m-m-1}.$ Let the sphere of radius $1$ centred at a word $x$ be denoted $V(x).$
Example: $x=000, V(x)=\{000,100,010,001\}.$
Enumerate the codewords as $c_1,\ldots,c_M$ and form an array with each row $V(c_i)$ for $i=1,\ldots,M.$
Clearly the vectors in each row are represented by $c_i$ which is at Hamming distance $\leq 1$ from them. Each $V(c_i)$ has $2^m-1+1=2^m$ entries. Since the code is perfect the union of all these $M$ disjoint lists $V(c_i)$ covers the whole space $\{0,1\}^{2^m-1}$ which numerically can be seen as well since $$ 2^{m}\times M=2^{m}\times 2^{2^m-1-m} = 2^{2^m-1}. $$
Now append a zero to the left of each vector in $V(c_i)$ for all $i$ and call this list $V_0(c_i)$. Also append a one to the left of each vector in $V(c_i)$ for all $i$ and call this list $V_1(c_i).$
This makes no difference to the distance properties above.
Generate an array of the form $$ \begin{array}{c} V_0(c_1)\\ V_1(c_1)\\ \vdots \\ V_0(c_M)\\ V_1(c_M) \end{array} $$ which has $2M=2^{2^m-m}$ rows. Recall $N=2^{2^m}.$ By the divisibility assumption we can now merge the rows above in groups of $2^{m}/m$ and obtain the array you want since each new row is still made up of either some Hamming codeword (with a prefix of 0 or 1) or one of its neighbours in the sphere of radius 1.
Hamming codewords can be efficiently generated by means of generating matrices.