/* Golomb ruler in Picat. A Golomb ruler is a set of integers (marks) a(1) < ... < a(n) such that all the differences a(i)-a(j) (i > j) are distinct. Clearly we may assume a(1)=0. Then a(n) is the length of the Golomb ruler. For a given number of marks, n, we are interested in finding the shortest Golomb rulers. Such rulers are called optimal. See http://www.research.ibm.com/people/s/shearer/grule.html Model created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ % Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/ import util. import cp. main => go. go => time2($golomb(8, Xs)), writeln(Xs). golomb(N, Xs) => writeln(n=N), Xs = new_list(N), NN = 2**(N-1)-1, Xs :: 0..NN, Xn #= Xs[N], % to minimize all_different(Xs), increasing(Xs), Xs[1] #= 0, Diffs = [Diff : I in 1..N, J in 1..N, I != J, Diff #= Xs[I]-Xs[J]], all_different(Diffs), % Symmetry breaking Diffs[1] #< Diffs[N], Xs[2] - Xs[1] #< Xs[N] - Xs[N-1], Vars = Diffs ++ Xs, solve([$min(Xn),ff,down],Vars). increasing(List) => foreach(I in 2..List.length) List[I-1] #=< List[I] end.