Download
/*

Magic sequence problem in Picat.

http://www.dcs.st-and.ac.uk/~ianm/CSPLib/prob/prob019/spec.html
"""
A magic sequence of length n is a sequence of integers x0 . . xn-1 between
0 and n-1, such that for all i in 0 to n-1, the number i occurs exactly xi
times in the sequence. For instance, 6,2,1,0,0,0,1,0,0,0 is a magic sequence
since 0 occurs 6 times in it, 1 occurs twice, ...

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 cp.

main => go.

go =>
magic_sequence(400,Sequence),
writeln(Sequence).

go2 =>
foreach(N in 4..40)
if magic_sequence(N,Sequence) then
writeln(Sequence)
else
writeln('No solution')
end
end.

scalar_product(A, X) = Product =>
Product #= sum([S : I in 1..A.length, S #= A[I]*X[I]]).

magic_sequence(N, Sequence) =>

writef("\n%d: ",N),

Sequence = new_list(N),
Sequence :: 0..N-1,

% Note: I would like to use global_cardinality/2 instead
%       but didn't get it right.
foreach(I in 0..N-1) count(I,Sequence,#=,Sequence[I+1]) end,

N #= sum(Sequence),
Integers = [ I : I in 0..N-1],
N = scalar_product(Integers, Sequence),
solve([ff], Sequence).