/*
Global constraint among_seq in Picat.
From Global constraint catalog:
http://www.emn.fr/x-info/sdemasse/gccat/Camong_seq.html
"""
Constraint
among_seq(LOW,UP,SEQ,VARIABLES,VALUES)
Purpose
Constrains all sequences of SEQ consecutive variables of the collection
VARIABLES to take at least LOW values in VALUES and at most UP values
in VALUES.
Example
(
1,2,4,<9,2,4,5,5,7,2>,
<0,2,4,6,8>
)
The among_seq constraint holds since the different sequences of 4
consecutive variables contains respectively 2, 2, 1 and 1 even numbers.
"""
Model created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
import cp.
main => go.
go ?=>
Len = 7,
% The set as a list
V = [0,2,4,6,8],
% create X
X = new_list(Len),
X :: 0..9,
% X = [9,2,4,5,5,7,2], % the example above
% some symmetry breaking if we let X free
all_different(X),
increasing(X),
Low = 1,
High = 2,
SeqLen = 4,
among_seq(Low,High,SeqLen,X,V),
% search
solve(X),
writeln([low=Low,high=High,seq_len=SeqLen]),
writeln(x=X),
writeln(v=V),
nl,
fail.
go => true.
/*
among_seq(Low, High, SeqLen, X, V)
See the definition above.
Ensures that all sequences of length SeqLen in the list X
contains at least Low and atmost High occurrences of V.
*/
among_seq(Low,High,SeqLen,X,V) =>
Len = X.length,
Size = Len-SeqLen+1,
foreach(I in 1..Size)
Seq = [X[J] : J in I..I+SeqLen-1],
among_range(Low, High, Seq, V)
end.
/*
among_range(Low, High, X, V)
ensures that the list X contains at least Low and atmost High
occurrences of V.
*/
among_range(Low, High,X,V) =>
Sum #= sum([B : El in X, B #<=> El in V]),
Sum #>= Low,
Sum #=< High.
increasing(List) =>
foreach(I in 2..List.length) List[I-1] #=< List[I] end.