/* 

  Non-continuous subsequences (Rosetta Code) in Picat.

  http://rosettacode.org/wiki/Non-continuous_subsequences
  """
  Consider some sequence of elements. (It differs from a mere set of elements by 
  having an ordering among members.)

  A subsequence contains some subset of the elements of this sequence, in the 
  same order.

  A continuous subsequence is one in which no elements are missing between the 
  first and last elements of the subsequence.

  Note: Subsequences are defined structurally, not by their contents. So a sequence a,b,c,d 
  will always have the same subsequences and continuous subsequences, no matter which values 
  are substituted; it may even be the same value.

  Task: Find all non-continuous subsequences for a given sequence. Example: For the sequence 
  1,2,3,4, there are five non-continuous subsequences, namely 1,3; 1,4; 2,4; 1,3,4 and 1,2,4.

  Goal: There are different ways to calculate those subsequences. Demonstrate algorithm(s) 
  that are natural for the language. 
  """

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

*/


import util.

main => go.


go =>
  println(1..4=non_cont(1..4)),
  
  L = "abcde".reverse(),
  println(L=non_cont(L)),

  println(ernit=non_cont("ernit")),
  println(aaa=non_cont("aaa")),
  println(aeiou=non_cont("aeiou")),

  nl,
  println("Printing just the lengths for 1..N for N = 1..20:"), 
  foreach(N in 1..20) 
    println(1..N=non_cont(1..N).length) % just the length
  end,

  nl.

% get all the non-continuous subsequences
non_cont(L) = [ [L[I] : I in S] : S in non_cont_ixs(L.length)].

% get all the index positions that are non-continuous
non_cont_ixs(N) = [ P:  P in power_set(1..N), length(P) > 1, P.last() - P.first() != P.length-1].