/* Recover origin of pair differences in Picat. From https://twitter.com/SturnioloSimone/status/1214588457135329280 """ Suppose there's a certain set of numbers - x_1, x_2, ..., x_n. You don't know n. Suppose you only know certain linear combinations of them, L_ij = x_i-x_j, but you DON'T know i or j. What's an algorithm to find as many of the xs as possible just from looking at the Ls? Ideas? ... (a follow up tweet:) There are four numbers. I can tell you that 1, 3, and 6 are differences between pairs of numbers chosen among them (you don't know which pairs). Can you tell me what the numbers are? Something like that, except you don't know it's four. """ A better description of the problem and findings can be found at http://hakank.org/picat/Recover_origin_of_pair_differences.pdf Also see the original model: http://hakank.org/picat/linear_combinations.pi This current model is a simplified 0/1 approach compared to the original model and what I can see it's faster on cases where max(Diffs) are not too large. For large max values it can be quite slow. This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import sat. % import cp. % import smt. % import mip. main => go. % % In this experiment we assume that there are no duplicates in the generating list, i.e. % that the duplicate list don't contains 0 (and has no duplicates). % go ?=> nolog, _ = random2(), % comment this for a static random seed. % Generate a problem: % L is the (random) generated list, Diffs are the differences of L, sorted and with duplicates remove % L = generate_problem(20,200), % remove duplicates % L := [99,100,101], % L := [I : I in 1..10], % L := [I : I in 1..41], % L := [2,3,5,7,11,13,17], % L := [sum([J : J in 1..I]) : I in 1..10], % L := [4,6,7], % L := [16,22,27,28,36,37,41,50,60,63,64,73,78,84,87,91,93,94], % L := [5, 14, 18, 34, 38, 49], % L := [5, 13, 19, 37, 48, 60, 86, 90, 98], % L := [13,28,46,67,71,73,75,81,91,96], % L := [4,10,12,19,27,28,34,41,43,44,52,53,60,61,77,80,96], % L := [1, 2, 5, 10, 15, 26, 37, 48, 54, 60, 66, 67, 68], % L := [3, 5, 13, 19, 37, 48, 56, 59, 60, 64, 66, 74, 77, 78, 80, 86, 90, 98], % L := [4, 7, 9, 11, 13, 15, 16, 18, 20, 22, 24, 29, 31, 33, 35, 38, 42, 44, 51], L := [40, 108, 122, 136, 141, 143, 146, 188, 192, 205, 259, 266, 287, 312, 330, 341, 349, 381, 386, 397, 429, 459, 475, 496], L := [40, 108, 122, 136, 141, 143, 146, 188, 192], % L := [16,41,43,54,56,62,66,67,84,95], % L := [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,173,174,175,176,177,178,179,180,181,182,183,184,185,187,188,189,190], % L := [1,4,8,9], % L := [1,3,8], println(l=L), Shifted=shifted_list(L), println(shifted=Shifted), Diffs = diffs(L), println(diffs=Diffs), % Opt=true, Opt = false, nl, linear_comb(Diffs, Opt, X, Z), % println(X), Sol = [I : I in 1..X.len, X[I] == 1], println(sol=Sol), println(z=Z), println(check=diffs(Sol)), if Sol == Shifted then println("We found it!") end, nl, fail, nl. go => true. go2 => nolog, Opt = true, foreach(N in 2..40) println(n=N), Diffs = [I : I in 1..N], linear_comb(Diffs,Opt, X, Z), % println(x=X), println([I : I in 1..X.len, X[I] == 1]), println(z=Z), nl end, nl. go3 => nolog, Opt = false, foreach(N in 2..40) println(n=N), Diffs = [I : I in 1..N], linear_comb(Diffs,Opt, X, Z), % println(x=X), println([I : I in 1..X.len, X[I] == 1]), println(z=Z), nl end, nl. % % The (sorted) pair differences of a list L. % pair_differences(L) = [abs(L[I]-L[J]) : I in 1..L.len, J in I+1..L.len].sort. % % (Theoretical) Minumum length of a origin list given a difference list of length Len . % min_len(Len) = floor(1+sqrt(1+8*Len)/2). % % Shifted (normalized) list of list L. % A shifted/normalized is a list which starts with 1 and ends with last(L)-L[1]+1 % shifted_list(L) = [L[I] - L[1] + 1 : I in 1..L.len]. % % Recover linear combinations (pairs of differences) % % Diffs : The list of differences % N : The length of X, the solution % Mode : - minimize: minimize the sum of the list differences in X % - all: find all solutions. A tip: for smaller problems is might be better to use the CP solver for this. % - first: find the first solution. Use SAT for large lists. % AllowDuplicates: Allow duplicates in Diffs if true. % Note: Even if AllowDuplicates is true, then we handle it as false if Diffs[1] > 0. % X : the solution, the "recovered" list % % % Note: This version use a 0/1 list for the used numbers % linear_comb(Diffs, Opt, X,Z)=> N = max(Diffs)+1, println(n=N), % Create the list X of decision variables of size N X = new_list(N), X :: 0..1, % Symmetry breaking: 1 is the first number. X[1] #= 1, % Since we start with 1, the last (and maximum) number in X is % max(Diffs) + 1 (which is the max domain value as well) X[N] #= 1, Z #= sum(X), MinLen = min_len(N), println(minLen=MinLen), % Z #>= MinLen, % NOTE: This don't always hold! % Ensure that we cover all the differences (in Diffs), % i.e. find some I and J (I 0 end, % All the differences from the pairs in the list X must be in the Diff list foreach(I in 1..N, J in I+1..N) % (X[I] #> 0 #/\ X[J] #> 0) #=> sum([D#=abs(I-J) : D in Diffs]) #> 0 % X[I] + X[J] #= 2 #=> sum([D#=abs(I-J) : D in Diffs]) #> 0 X[I] * X[J] #= 1 #=> sum([D #= abs(I-J) : D in Diffs]) #> 0 % (X[I] #/\ X[J]) #=> sum([D#=abs(I-J) : D in Diffs]) #> 0 end, % Solve % Vars = X ++ Ts ++ IJs, println(solve), Vars = X, if Opt then solve($[min,split, min(Z), report(printf("Z:%d X: %w\n", Z, X))],Vars) else Vars := X ++ [Z], solve($[split],Vars) end. % % Return the list difference of a list L % diffs(L) = Diffs => Len = L.len, Diffs1 = [], foreach(I in 1..Len, J in I+1..Len) Diffs1 := Diffs1 ++ [abs(L[I]-L[J])] end, Diffs = Diffs1.sort_remove_dups. % Don't remove duplicates % Experimental diffs2(L) = Diffs => Len = L.len, Diffs1 = [], foreach(I in 1..Len, J in I+1..Len) Diffs1 := Diffs1 ++ [abs(L[I]-L[J])] end, Diffs = Diffs1.sort. % % Generate a random problem instance of (at least) length N % % Sort and remove all duplicates generate_problem(N,MaxVal) = [1+random() mod MaxVal : _ in 1..N].sort_remove_dups. % Sort and keep duplicates. generate_problem2(N,MaxVal) = [1+random() mod MaxVal : _ in 1..N].sort.