/* Reconstruction permutations in Picat. Via https://github.com/maxtuno/PEQNP/blob/master/examples/permutations_reconstruction_experiment.py """ Permutation Reconstruction fromDifferences from https://arxiv.org/pdf/1410.6396.pdf """ https://arxiv.org/pdf/1410.6396.pdf: Marzio De Biasi: "Permutation Reconstruction fromDifferences" """ Abstract: We prove that the problem of reconstructing a permutation p1,...,pn of the integers [1...n] given the absolute differences|pi+1−pi|,i= 1,...,n−1 is NP–complete. As an intermediate step we first prove the NP–completeness of the decision version of a new puzzle game that we call Crazy Frog Puzzle. The permutation reconstruction from differences is one of the simplest combinatorial problems that have been proved to be computationally intractable. """ The model is very straight forward: - input: generate a permutation of size N and pick the differences (size N-1) - now we create a list of N * ensure that they are all distinct (all_different/1 or all_distinct/1) * ensure that all the differences in this list are the same as the input list of differences * Times for the instances 2..N for CP solver with a 20s timeout using all_different/1 and ff+split 1..276 in 1min 41.4s [2 = 1,3 = 0,4 = 0,5 = 1,6 = 0,7 = 0,8 = 0,9 = 0,10 = 0,11 = 1,12 = 1,13 = 0,14 = 0,15 = 0,16 = 0,17 = 0,18 = 0,19 = 0,20 = 1,21 = 0,22 = 0,23 = 0,24 = 1,25 = 0,26 = 0,27 = 1,28 = 1,29 = 0,30 = 1,31 = 0,32 = 0,33 = 1,34 = 0,35 = 0,36 = 1,37 = 0,38 = 1,39 = 1,40 = 1,41 = 1,42 = 0,43 = 0,44 = 0,45 = 0,46 = 1,47 = 1,48 = 0,49 = 2,50 = 1,51 = 0,52 = 1,53 = 1,54 = 0,55 = 2,56 = 0,57 = 1,58 = 2,59 = 1,60 = 2,61 = 0,62 = 1,63 = 2,64 = 2,65 = 8,66 = 2,67 = 3,68 = 1,69 = 0,70 = 2,71 = 2,72 = 2,73 = 2,74 = 3,75 = 1,76 = 4,77 = 4,78 = 3,79 = 2,80 = 4,81 = 4,82 = 2,83 = 2,84 = 3,85 = 12,86 = 1,87 = 13,88 = 3,89 = 4,90 = 5,91 = 2,92 = 2,93 = 3,94 = 2,95 = 3,96 = 21,97 = 3,98 = 4,99 = 3,100 = 7,101 = 2,102 = 10,103 = 0,104 = 1,105 = 2,106 = 4,107 = 7,108 = 2,109 = 2,110 = 4,111 = 3,112 = 6,113 = 6,114 = 25,115 = 2,116 = 21,117 = 15,118 = 9,119 = 3,120 = 5,121 = 5,122 = 40,123 = 21,124 = 6,125 = 3,126 = 9,127 = 7,128 = 8,129 = 4,130 = 10,131 = 2,132 = 11,133 = 30,134 = 24,135 = 5,136 = 72,137 = 24,138 = 5,139 = 12,140 = 17,141 = 4,142 = 38,143 = 8,144 = 70,145 = 4,146 = 28,147 = 5,148 = 52,149 = 11,150 = 65,151 = 2,152 = 123,153 = 1,154 = 0,155 = 2,156 = 18,157 = 23,158 = 10,159 = 5,160 = 116,161 = 17,162 = 87,163 = 4,164 = 3,165 = 41,166 = 27,167 = 68,168 = 6,169 = 121,170 = 8,171 = 47,172 = 8,173 = 111,174 = 253,175 = 4,176 = 31,177 = 12,178 = 89,179 = 36,180 = 35,181 = 15,182 = 79,183 = 16,184 = 3,185 = 10224,186 = 491,187 = 166,188 = 4,189 = 16,190 = 40,191 = 80,192 = 7,193 = 14,194 = 54,195 = 284,196 = 17,197 = 30,198 = 900,199 = 1,200 = 48,201 = 25,202 = 58,203 = 6,204 = 6,205 = 91,206 = 4,207 = 114,208 = 37,209 = 45,210 = 5,211 = 98,212 = 7,213 = 624,214 = 28,215 = 96,216 = 430,217 = 613,218 = 75,219 = 21,220 = 18,221 = 1035,222 = 72,223 = 9,224 = 44,225 = 18,226 = 28,227 = 40,228 = 33,229 = 90,230 = 15,231 = 11,232 = 256,233 = 29,234 = 15,235 = 263,236 = 1498,237 = 656,238 = 69,239 = 81,240 = 418,241 = 51,242 = 194,243 = 1040,244 = 32,245 = 90,246 = 62,247 = 24,248 = 68,249 = 890,250 = 360,251 = 135,252 = 437,253 = 641,254 = 8,255 = 478,256 = 355,257 = 270,258 = 7053,259 = 7471,260 = 143,261 = 40,262 = 3023,263 = 615,264 = 53,265 = 1178,266 = 1693,267 = 94,268 = 6220,269 = 54,270 = 8,271 = 6707,272 = 703,273 = 17290,274 = 7,275 = 191,276 = 29] picat reconstruction_permutations.pi 101,06s user 0,40s system 100% cpu 1:41,40 total Some other runs * 1..292 in 1min 26s * 1..262 in 1min 27s * 1..285 in 1min 24s using new_array/1 instead of new_list/1: * 1..310 in 1min 32s * 1..295 in 1min 49s * 1..248 in 42s * 1..263 in 47s * Times for the instances 2..N for CP solver with a 20s timeout using all_distinct/1 and ff+split: This is generally a bit slower (not unexpected since all_distinct propagates harder). 1..228 in 2min 32.8s [2 = 0,3 = 1,4 = 0,5 = 0,6 = 1,7 = 0,8 = 0,9 = 1,10 = 1,11 = 1,12 = 1,13 = 1,14 = 0,15 = 0,16 = 0,17 = 1,18 = 1,19 = 1,20 = 0,21 = 0,22 = 1,23 = 0,24 = 0,25 = 1,26 = 1,27 = 1,28 = 0,29 = 0,30 = 0,31 = 1,32 = 1,33 = 2,34 = 0,35 = 1,36 = 1,37 = 2,38 = 1,39 = 1,40 = 1,41 = 1,42 = 1,43 = 0,44 = 3,45 = 0,46 = 2,47 = 1,48 = 4,49 = 2,50 = 0,51 = 0,52 = 2,53 = 1,54 = 1,55 = 2,56 = 5,57 = 1,58 = 4,59 = 2,60 = 4,61 = 8,62 = 7,63 = 3,64 = 7,65 = 3,66 = 11,67 = 15,68 = 7,69 = 6,70 = 8,71 = 8,72 = 3,73 = 17,74 = 1,75 = 8,76 = 5,77 = 8,78 = 12,79 = 5,80 = 9,81 = 6,82 = 20,83 = 8,84 = 11,85 = 4,86 = 30,87 = 6,88 = 43,89 = 11,90 = 1,91 = 2,92 = 21,93 = 33,94 = 15,95 = 7,96 = 10,97 = 8,98 = 5,99 = 30,100 = 11,101 = 13,102 = 28,103 = 30,104 = 33,105 = 7,106 = 80,107 = 27,108 = 42,109 = 19,110 = 70,111 = 8,112 = 7,113 = 18,114 = 28,115 = 54,116 = 25,117 = 26,118 = 43,119 = 10,120 = 51,121 = 291,122 = 137,123 = 10,124 = 56,125 = 8,126 = 22,127 = 30,128 = 33,129 = 371,130 = 12,131 = 69,132 = 424,133 = 166,134 = 940,135 = 89,136 = 20,137 = 22,138 = 21,139 = 33,140 = 15,141 = 18,142 = 74,143 = 80,144 = 32,145 = 31,146 = 27,147 = 1341,148 = 93,149 = 94,150 = 117,151 = 253,152 = 46,153 = 429,154 = 682,155 = 192,156 = 31,157 = 91,158 = 114,159 = 9014,160 = 128,161 = 386,162 = 991,163 = 115,164 = 188,165 = 38,166 = 414,167 = 178,168 = 961,169 = 16,170 = 281,171 = 392,172 = 416,173 = 1024,174 = 524,175 = 5874,176 = 402,177 = 57,178 = 178,179 = 25,180 = 6249,181 = 96,182 = 525,183 = 429,184 = 504,185 = 276,186 = 1310,187 = 67,188 = 40,189 = 143,190 = 1261,191 = 639,192 = 443,193 = 82,194 = 1908,195 = 64,196 = 12367,197 = 365,198 = 271,199 = 128,200 = 81,201 = 3224,202 = 141,203 = 6158,204 = 341,205 = 261,206 = 71,207 = 18674,208 = 324,209 = 13011,210 = 110,211 = 164,212 = 656,213 = 638,214 = 2940,215 = 100,216 = 10596,217 = 4831,218 = 435,219 = 317,220 = 453,221 = 121,222 = 329,223 = 4893,224 = 835,225 = 3108,226 = 182,227 = 285,228 = 363] picat reconstruction_permutations.pi 152,69s user 0,16s system 100% cpu 2:32,82 total Some other runs: * 1..215 in 1min 32s * 1..192 in 1min 1s * 1..187 in 34.9s * The SAT solver is not doing so great on this (timeout 20s): 1..88 in 4min 31s [2 = 0,3 = 1,4 = 0,5 = 1,6 = 2,7 = 1,8 = 2,9 = 3,10 = 5,11 = 4,12 = 3,13 = 4,14 = 3,15 = 4,16 = 14,17 = 7,18 = 40,19 = 7,20 = 5,21 = 106,22 = 113,23 = 103,24 = 30,25 = 10,26 = 8,27 = 12,28 = 148,29 = 15,30 = 170,31 = 220,32 = 22,33 = 529,34 = 657,35 = 14,36 = 485,37 = 386,38 = 195,39 = 195,40 = 776,41 = 54,42 = 27,43 = 1002,44 = 731,45 = 308,46 = 1472,47 = 107,48 = 275,49 = 771,50 = 246,51 = 109,52 = 400,53 = 351,54 = 2620,55 = 313,56 = 669,57 = 268,58 = 7649,59 = 6865,60 = 6726,61 = 7280,62 = 857,63 = 9058,64 = 606,65 = 1654,66 = 7265,67 = 248,68 = 10203,69 = 8775,70 = 7637,71 = 1990,72 = 8622,73 = 11074,74 = 1303,75 = 8824,76 = 9056,77 = 12979,78 = 9718,79 = 8606,80 = 429,81 = 8830,82 = 12847,83 = 15752,84 = 11344,85 = 3460,86 = 9796,87 = 14736,88 = 11485] picat reconstruction_permutations.pi 270,36s user 0,60s system 100% cpu 4:30,96 total Some other runs: * 1..105 in 7min 21s * 1..115 in 9min 11s Timeout 60s, CP [2 = 0,3 = 0,4 = 0,5 = 0,6 = 0,7 = 0,8 = 0,9 = 0,10 = 0,11 = 0,12 = 0,13 = 0,14 = 0,15 = 0,16 = 0,17 = 0,18 = 0,19 = 0,20 = 1,21 = 0,22 = 0,23 = 0,24 = 1,25 = 0,26 = 0,27 = 1,28 = 0,29 = 1,30 = 0,31 = 0,32 = 1,33 = 0,34 = 1,35 = 0,36 = 0,37 = 1,38 = 0,39 = 0,40 = 1,41 = 0,42 = 1,43 = 0,44 = 0,45 = 2,46 = 1,47 = 0,48 = 1,49 = 1,50 = 1,51 = 0,52 = 1,53 = 1,54 = 1,55 = 1,56 = 1,57 = 1,58 = 1,59 = 0,60 = 2,61 = 5,62 = 0,63 = 2,64 = 5,65 = 1,66 = 0,67 = 1,68 = 2,69 = 1,70 = 1,71 = 2,72 = 2,73 = 6,74 = 1,75 = 2,76 = 1,77 = 1,78 = 8,79 = 2,80 = 2,81 = 0,82 = 3,83 = 0,84 = 2,85 = 1,86 = 1,87 = 7,88 = 33,89 = 3,90 = 2,91 = 1,92 = 1,93 = 3,94 = 3,95 = 1,96 = 2,97 = 8,98 = 1,99 = 4,100 = 1,101 = 11,102 = 40,103 = 3,104 = 4,105 = 8,106 = 1,107 = 2,108 = 3,109 = 1,110 = 5,111 = 4,112 = 2,113 = 4,114 = 4,115 = 3,116 = 2,117 = 7,118 = 2,119 = 2,120 = 5,121 = 10,122 = 1,123 = 1,124 = 6,125 = 10,126 = 12,127 = 14,128 = 3,129 = 6,130 = 10,131 = 2,132 = 2,133 = 4,134 = 1,135 = 6,136 = 4,137 = 4,138 = 2,139 = 7,140 = 21,141 = 6,142 = 58,143 = 53,144 = 9,145 = 9,146 = 6,147 = 6,148 = 68,149 = 8,150 = 32,151 = 67,152 = 7,153 = 7,154 = 3,155 = 2,156 = 10,157 = 2,158 = 4,159 = 124,160 = 4,161 = 84,162 = 3,163 = 30,164 = 3,165 = 7,166 = 5,167 = 36,168 = 3,169 = 57,170 = 6,171 = 7,172 = 14,173 = 2,174 = 309,175 = 2,176 = 12,177 = 18,178 = 13,179 = 27,180 = 34,181 = 11,182 = 66,183 = 2388,184 = 18,185 = 94,186 = 6,187 = 15,188 = 4,189 = 6965,190 = 22,191 = 62,192 = 1366,193 = 9,194 = 10,195 = 5,196 = 13,197 = 49,198 = 4,199 = 29,200 = 19,201 = 11,202 = 5848,203 = 55,204 = 35,205 = 45,206 = 17,207 = 19,208 = 2824,209 = 282,210 = 147,211 = 14,212 = 191,213 = 13,214 = 17,215 = 40,216 = 45,217 = 54,218 = 41,219 = 6,220 = 10,221 = 4,222 = 282,223 = 16,224 = 46,225 = 13,226 = 56,227 = 4,228 = 26,229 = 195,230 = 7,231 = 79,232 = 4,233 = 185,234 = 13,235 = 40,236 = 8,237 = 22,238 = 153,239 = 45,240 = 113,241 = 64,242 = 12,243 = 1648,244 = 9,245 = 1230,246 = 360,247 = 6,248 = 189,249 = 38,250 = 55,251 = 491,252 = 24,253 = 141,254 = 23,255 = 39,256 = 5,257 = 21,258 = 23,259 = 62,260 = 1170,261 = 56,262 = 435,263 = 683,264 = 53,265 = 96,266 = 902,267 = 552,268 = 1004,269 = 586,270 = 567,271 = 593,272 = 191,273 = 21,274 = 12,275 = 146,276 = 1162,277 = 14,278 = 12,279 = 41,280 = 116,281 = 15,282 = 115,283 = 8,284 = 1266,285 = 121,286 = 2711,287 = 10,288 = 305,289 = 28,290 = 64,291 = 70,292 = 22,293 = 22,294 = 262,295 = 67,296 = 679,297 = 14,298 = 23,299 = 49,300 = 9] 1..300: 1 min 42s Timeout 600s (10 minutes) This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import cp,util. % import sat,util. main => go. % % Find solutions for size 1..?. Finish whenever a timeout is reached. % Note that the input list (Diffs) is a permutation. % go => _ = random2(), % Sizes = [], Times = new_map(), N = 0, TimeoutS = 600, % timeout in seconds Timeout = TimeoutS*1000, % in mililis while (true) N := N+1, println(size=N), % Generate the problem instance Diffs = gen_instance(N), % println(diffs=Diffs), % Solve the problem for only one solution. % Finish if timeout. if [EndTime,_Backtracks,Status] = time2f($solve_perm(Diffs,N, X), Timeout) then println([n=N,time_ms=EndTime,status=Status]), if Status != success then println("No solve!"), println([NN=Times.get(NN) : NN in 2..N-1]), halt end, XX = [abs(X[I]-X[I+1]) : I in 1..N-1], if XX == Diffs then % println(x=X), % println(xx=XX), println("OK"), Times.put(N,EndTime) else println("NOT EQUAL!"), println([NN=Times.get(NN) : NN in 2..N-1]), halt end else println("no solve!"), halt end end, nl. % % This variant does not require that the input list (Diffs) % is a permutation. See https://mathoverflow.net/questions/135968/how-hard-is-reconstructing-a-permutation-from-its-differences-sequence % for a little more about this. % Also see: % %https://cstheory.stackexchange.com/questions/18255/efficient-algorithm-for-existence-of-permutation-with-differences-sequence go2 => _ = random2(), M = 5, % We are looking for a permutation of length M Diffs = gen_instance2(M-1,M-1), % Generate a random instance of difference (length M-1) % Diffs := [1,1,3], println(diffs=Diffs), Len = Diffs.len, if solve_perm(Diffs,Len+1,X) then println(X) end, nl. % % Generate permutations of 1..N and show differences, difference of difference % as well as their sums. % [[1,2,3,4],[1,1,1],3,[0,0],0] % [[2,1,3,4],[1,2,1],4,[1,1],2] % [[2,3,1,4],[1,2,3],6,[1,1],2] % [[2,3,4,1],[1,1,3],5,[0,2],2] % [[1,3,2,4],[2,1,2],5,[1,1],2] % [[3,1,2,4],[2,1,2],5,[1,1],2] % [[3,2,1,4],[1,1,3],5,[0,2],2] % [[3,2,4,1],[1,2,3],6,[1,1],2] % [[1,3,4,2],[2,1,2],5,[1,1],2] % [[3,1,4,2],[2,3,2],7,[1,1],2] % [[3,4,1,2],[1,3,1],5,[2,2],4] % [[3,4,2,1],[1,2,1],4,[1,1],2] % [[1,2,4,3],[1,2,1],4,[1,1],2] % [[2,1,4,3],[1,3,1],5,[2,2],4] % [[2,4,1,3],[2,3,2],7,[1,1],2] % [[2,4,3,1],[2,1,2],5,[1,1],2] % [[1,4,2,3],[3,2,1],6,[1,1],2] % [[4,1,2,3],[3,1,1],5,[2,0],2] % [[4,2,1,3],[2,1,2],5,[1,1],2] % [[4,2,3,1],[2,1,2],5,[1,1],2] % [[1,4,3,2],[3,1,1],5,[2,0],2] % [[4,1,3,2],[3,2,1],6,[1,1],2] % [[4,3,1,2],[1,2,1],4,[1,1],2] % [[4,3,2,1],[1,1,1],3,[0,0],0] go3 => N = 5, foreach(P in permutations(1..N)) Diffs1 = diffs(P), Diffs2 = diffs(Diffs1), println([P,Diffs1,sum(Diffs1),Diffs2,sum(Diffs2)]) end, nl. % % Generate all combinations of 1..N to recover a permutation of 1..N+1 % % [1,1,1] = [{1,2,3,4},{4,3,2,1}] % [1,1,2] = [] % [1,1,3] = [{3,2,1,4},{2,3,4,1}] % [1,2,1] = [{1,2,4,3},{2,1,3,4},{3,4,2,1},{4,3,1,2}] % [1,2,2] = [] % [1,2,3] = [{3,2,4,1},{2,3,1,4}] % [1,3,1] = [{2,1,4,3},{3,4,1,2}] % [1,3,2] = [] % [1,3,3] = [] % [2,1,1] = [] % [2,1,2] = [{1,3,2,4},{1,3,4,2},{2,4,3,1},{3,1,2,4},{4,2,1,3},{4,2,3,1}] % [2,1,3] = [] % [2,2,1] = [] % [2,2,2] = [] % [2,2,3] = [] % [2,3,1] = [] % [2,3,2] = [{2,4,1,3},{3,1,4,2}] % [2,3,3] = [] % [3,1,1] = [{1,4,3,2},{4,1,2,3}] % [3,1,2] = [] % [3,1,3] = [] % [3,2,1] = [{1,4,2,3},{4,1,3,2}] % [3,2,2] = [] % [3,2,3] = [] % [3,3,1] = [] % [3,3,2] = [] % [3,3,3] = [] % % Thus for N=3: [2 = 7,4 = 1,6 = 1,total_diffs = 27,total_sols = 9] % % Distribution of solutions: % Number of solutions=Count, total_diffs , total sols % N Dist % ---------- % 2 [2 = 3,total_diffs = 4,total_sols = 3] % 3 [2 = 7,4 = 1,6 = 1,total_diffs = 27,total_sols = 9] % 4 [2 = 48,4 = 6,total_diffs = 256,total_sols = 54] % 5 [2 = 192,4 = 60,6 = 12,8 = 3,total_diffs = 3125,total_sols = 267] % 6 [2 = 1850,4 = 283,6 = 28,8 = 5,total_diffs = 46656,total_sols = 2166] % 7 [2 = 12536,4 = 2528,6 = 521,8 = 111,10 = 44,12 = 24,14 = 11,16 = 6,18 = 3,20 = 3,30 = 1,total_diffs = 823543,total_sols = 15788] % 8 [2 = 141006,4 = 17834,6 = 828,8 = 508,10 = 26,12 = 20,total_diffs = 16777216,total_sols = 160222] % 9 % 10 % go4 ?=> % Generate difference of length N % for recovering a permutation of length N+1 N = 9, Map = get_global_map(), Map.put(total_diffs,0), Map.put(total_sols,0), println(n=N), Diffs = new_list(N), Diffs :: 1..N, solve($[ff,split],Diffs), Diffs2 = diffs(Diffs), All = findall(X,solve_perm(Diffs,N+1,X)), Map.put(total_diffs,Map.get(total_diffs)+1), if All != [] then % println([Diffs,Diffs2,All,len=All.len]), Map.put(All.len,Map.get(All.len,0)+1), Map.put(total_sols,Map.get(total_sols)+1), end, fail, nl. go4 => Map = get_global_map(), println([Key=Map.get(Key) : Key in Map.keys.sort]), nl. diffs(L) = [abs(L[I]-L[I-1]) : I in 2..L.len]. % % Solve the problem. % solve_perm(Diffs,N, X) => X = new_array(N), X :: 1..N, all_different(X), % all_different/1 is quite much faster % all_distinct(X), % Ensure that the ith value in the difference lists % is the ith difference in the solution foreach(I in 1..N-1) Diffs[I] #= abs(X[I]-X[I+1]) end, solve($[ff,split],X). gen_instance(N) = D => L = shuffle(1..N), D = [abs(L[I]-L[I-1]) : I in 2..N]. % Generate a random sorted instance allowing duplicates gen_instance2(N,Max) = [1+ random() mod Max : _ in 1..N].sort. % % Randomly shuffle a list. % shuffle(List) = List2 => List2 = List, Len = List.length, foreach(I in 1..Len) R2 = 1+(random() mod Len), List2 := swap(List2,I,R2) end. % % Swap position I <=> J in list L % swap(L,I,J) = L2 => L2 = L, T = L2[I], L2[I] := L2[J], L2[J] := T. % % Returns the time, backtrack and status of a call % time2f(Goal,Timeout) = [End,Backtracks,Status] => statistics(runtime,_), statistics(backtracks, Backtracks1), time_out(Goal,Timeout,Status), statistics(backtracks, Backtracks2), statistics(runtime, [_,End]), Backtracks = Backtracks2 - Backtracks1.