// A332263 - Maximal length of a string over the alphabet {0,1,2} with the property that its // contiguous substrings of length n all have different quantities of 0's, 1's, or 2's. // // C++ program by Bert Dobbelaere // // Lexicographically minimal strings achieving maximum length: // // N=1 L=3 012 // A332263(1) = 3 // N=2 L=7 0011220 // A332263(2) = 7 // N=3 L=12 011122200012 // A332263(3) = 12 // N=4 L=17 00111122220000121 // A332263(4) = 17 // N=5 L=22 0001111122222000001211 // A332263(5) = 22 // N=6 L=30 001011112122220200001012120200 // A332263(6) = 30 // N=7 L=39 001011111212222202000001011212022010010 // A332263(7) = 39 // N=8 L=45 000010111111212222220200000010121212022001001 // A332263(8) = 45 // N=9 L=56 00102221011211000200102222121211111010000000202222222121 // A332263(9) = 56 // N=10 L=66 001000112212022122000010020111112221222222000000000011111111112002 // A332263(10) = 66 // N=11 L=77 00010111111111212222222200200000000110111121120212222020010001012112021202000 // A332263(11) = 77 // N=12 L=90 000101011111111212122222222020200000000101011112112022122220200100200101012211012220200100 // A332263(12) = 90 #include #define MAX_N 15 #define MAX_A 1000 #define S0 0 #define S1 1 #define S2 (MAX_N+1) // Trace elements contain 0 (='0'), 1 (='1') or (MAX_N+1) to represent '2'. // Sum of N consecutive elements is unique for each combination of symbols this way int trace[MAX_A+1]; bool signature[MAX_N*S2+1]; int N; int maxlen=0; void dump(int l) { printf("N=%d L=%d ",N,l); for(int b=0;bmaxlen) { dump(l); maxlen=l; } signature[sig_in] = true; int s = sig_in - trace[l-N]; // Remove oldest element from window trace[l]=S0; solve(l+1, s+S0); trace[l]=S1; solve(l+1, s+S1); trace[l]=S2; solve(l+1, s+S2); // Minor loss in efficiency if no 1 was encountered so far signature[sig_in] = false; } // First window filler void solveStart(int l, int sig_in, bool used_1) { if(l<(N-1)) { // Logic ensures that the first 0, 1 and 2 appear in sorted order trace[l]=S0; solveStart(l+1, sig_in+S0, used_1); trace[l]=S1; if(l>0){solveStart(l+1, sig_in+S1, true);} if(used_1) { trace[l]=S2; solveStart(l+1, sig_in+S2, true); } } else // Fill last element of 1st window, then continue with inner search routine { trace[l]=S0; solve(l+1, sig_in+S0); trace[l]=S1; solve(l+1, sig_in+S1); trace[l]=S2; solve(l+1, sig_in+S2); // Minor loss in efficiency if no 1 was encountered so far } } int main() { for(N=1;N<=MAX_N;N++) { maxlen=0; for(int s=0;s <= MAX_N*S2 ; s++ ) signature[s]=false; solveStart(0, 0, false); printf("A332263(%d) = %d\n",N,maxlen); } return 0; }