/* 

  Subsequence in Picat.

  A sequence sub_seq is a subsequence of seq when all values in sub_seq are 
  exactly in the same order as in seq.


  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import cp.

main => go.

go =>
  Seq = [5,4,1,5,2,1],
  M = 4,
  println(seq=Seq),
  println(m=M),
  
  subsequence_solve(Seq,M, SubSeq),
  println('subseq '=SubSeq),
  fail,
  nl.  


go2 =>
  _ = random2(),
  N = 1000,
  M = 14,
  Seq = [random(1,N) : _ in 1..N],
  println(seq=Seq),
  println(m=M),

  subsequence_solve(Seq,M, SubSeq),
  println(subseq=SubSeq),
  fail,
  nl.  

subsequence_solve(Seq,M, SubSeq) =>

  SubSeq = new_list(M), 
  SubSeq :: min(Seq)..max(Seq),

  subsequence(Seq,SubSeq),

  solve($[ff,split],SubSeq).


%
% Sums the sequence sub_seq in an sub sequence of seq
%
subsequence(Seq, SubSeq) =>
  N = Seq.len,
  M = SubSeq.len,
  Offset :: 0..N-M, % offset in seq
  % identify the positions in seq for all elements in sub_seq
  foreach(I in 1..M)
    OffsetI #= Offset+I,
    element(OffsetI,Seq,SubSeq[I])
   end.