/* Low autocorrelation binary sequences (CSPLib #005) in Picat. http://www.csplib.org/Problems/prob005/ """ These problems have many practical applications in communications and electrical engineering. The objective is to construct a binary sequence Si of length n that minimizes the autocorrelations between bits. Each bit in the sequence takes the value +1 or -1. With non-periodic (or open) boundary conditions, the k-th autocorrelation, Ck is defined to be ∑i=0..n−k−1 (Si∗Si+k). With periodic (or cyclic) boundary conditions, the k-th autocorrelation, Ck is defined to be ∑i=0..(n−1) (si∗si+k mod n). The aim is to minimize the sum of the squares of these autocorrelations. That is, to minimize E = ∑k=1..(n−1) (Ck)^2. """ From Iván Dotu, Pascal Van Hentenryck: A Note on Low Autocorrelation Binary Sequences: """ n E F ------- 21 26 8.48 22 39 6.21 23 47 5.63 24 36 8.00 25 36 8.68 ... """ According to Mertens "Exhaustive Search for Low Autocorrelation Binary Sequences" F (n^2 / 2*E) should be about 9.3 for open problems. From the result page: http://www.csplib.org/Problems/prob005/results """ n E(s) F(s) Runtime Limit Best Found LABS in Run Length Notation 61 226 8.23 3 m 1.1 h 33211112111235183121221111311311 62 235 8.18 8 m 1.5 h 112212212711111511121143111422321 63 207 9.59 4 m 2.0 h 2212221151211451117111112323231 64 208 9.85 47 m 2.7 h 223224111341121115111117212212212 65 240 8.80 2.2 h 3.7 h 132323211111711154112151122212211 66 265 8.22 3.1 h 4.9 h 24321123123112112124123181111111311 67 241 9.31 4.1 h 6.6 h 12112111211222B2221111111112224542 68 250 9.25 6.6 h 8.8 h 11111111141147232123251412112221212 69 274 8.69 8.2 h 11.8 h 111111111141147232123251412112221212 70 295 8.31 12.4 h 15.8 h 232441211722214161125212311111111 ------------------------------------------------------------------------ 71 275 9.17 7.8 h 10.0 h 241244124172222111113112311211231121 72 300 8.64 2.4 h 10.0 h 1111114111444171151122142122224222 73 308 8.65 1.2 h 10.0 h 1111112311231122113111212114171322374 74 349 7.85 0.2 h 10.0 h 11321321612333125111412121122511131111 75 341 8.25 8.0 h 10.0 h 12122132121211211111131111618433213232 76 338 8.54 4.6 h 10.0 h 111211112234322111134114212211221311B11 77 366 8.10 3.9 h 10.0 h 111111191342222431123312213411212112112 """ Results from this model (problem type open) [n=2,e=1,f=2.0,time=0.0] [n=3,e=1,f=4.5,time=0.0] [n=4,e=2,f=4.0,time=0.0] [n=5,e=2,f=6.25,time=0.0] [n=6,e=7,f=2.571428571428572,time=0.0] [n=7,e=3,f=8.166666666666666,time=0.004] [n=8,e=8,f=4.0,time=0.0] [n=9,e=12,f=3.375,time=0.004] [n=10,e=13,f=3.846153846153846,time=0.004] [n=11,e=5,f=12.1,time=0.016] [n=12,e=10,f=7.2,time=0.008] [n=13,e=6,f=14.083333333333334,time=0.004] [n=14,e=19,f=5.157894736842105,time=0.06] [n=15,e=15,f=7.5,time=0.116] [n=16,e=24,f=5.333333333333333,time=0.256] [n=17,e=32,f=4.515625,time=0.744] [n=18,e=25,f=6.48,time=0.62] [n=19,e=29,f=6.224137931034483,time=2.36] [n=20,e=26,f=7.692307692307693,time=2.004] [n=21,e=26,f=8.48076923076923,time=4.02] [n=22,e=39,f=6.205128205128205,time=11.249000000000001] [n=23,e=47,f=5.627659574468085,time=32.805999999999997] [n=24,e=36,f=8.0,time=35.630000000000003] [n=25,e=36,f=8.680555555555555,time=70.748999999999995] [n=26,e=45,f=7.511111111111111,time=104.013999999999996] [n=27,e=37,f=9.851351351351351,time=405.069000000000017] [n=28,e=50,f=7.84,time=510.355999999999995] [n=29,e=62,f=6.782258064516129,time=1049.097999999999956] [n=30,e=59,f=7.627118644067797,time=1547.18100000000004] [n=31,e=67,f=7.171641791044777,time=4855.386999999999716] This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import cp. % import sat. % import mip. main => time2(go). go => N = 21, labs(N, open, _S,_C,_E,_F), nl. go2 => Es = [], foreach(N in 2..31) println(n=N), statistics(runtime,_), labs(N,open, _S,_C,E,F), statistics(runtime, [_,End]), T = End / 1000.0, printf("Time: %0.4fs\n\n", T), Es := Es ++ [[n=N,e=E,f=F,time=T]] end, foreach(R in Es) println(R) end, nl. labs(N,Type, S,C,E,F) => % Note: The arrays are 1-based. S = new_list(N), S :: [-1,1], C = new_list(N), C :: -N..N, foreach(K in 1..N) if Type == open then C[K] #= sum([S[I]*S[I+K] : I in 1..N-K]) % non-periodic (open) else C[K] #= sum([S[I]*S[1+((I+K-1) mod N)] : I in 1..N]) % periodic (cyclic) end end, E #= sum([C[K]*C[K] : K in 1..N]), Vars = C ++ S, solve($[ff,reverse_split,min(E), report(printf("E: %d\n", E))], Vars), % 4.2s on n=21 println(s=S), println(c=C), println(e=E), F = (N*N/(2*E)), println(f=F), nl.