Download
/*
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.