Saturday, September 28, 2013

Terms with Variables

Cosineau and Mauny present a type suitable for modeling terms with variables convenient for applications involving variables and substitutions. It is defined like this:
(*term_types.ml*)
type (α, β) term = 
| Term of α * (α, β) term list
| Var of β

Analyzing syntax

To proceed, let us restrict our attention to the type (string, string) term. The concrete syntax we use for such expressions is parenthesized.
  • a (t1, ..., tn) is the syntax of Term (a, [t1; ...; tn])
We disambiguate variables from constants by representing constants as functions applied to an empty list of arguments
  • a (b (), c) is the syntax of Term ("a", [Term ("b", []); Var "c"])
We start towards a function to analyze syntax. First the lexer.
(*lexer.mll*)
{
  open Parser  (*The type token is defined in parser.mli.*)
}

let alpha=['a'-'z' 'A'-'Z']

rule token = parse
    [' ' '\t' '\n']         (* skip blanks *) { token lexbuf }
  | '('                                             { LPAREN }
  | ')'                                             { RPAREN }
  | ','                                              { COMMA }
  | ((alpha)(alpha)*) as s                         { STRING s}
  | eof                                                { EOI }
Now the parser.
/*parser.mly*/

%token  STRING
%token LPAREN RPAREN COMMA EOI

%start main
%type <(string, string) Term_types.term> main
%%
main:
 | exp EOI { $1 }
 ;
exp:
 | tag exp_more           
     { 
       match $2 with
       | None -> Term_types.Var $1
       | Some l -> Term_types.Term ($1, l)
     }
 ;
exp_more:
 | /*nothing*/ { None }
 | LPAREN exp_list RPAREN { Some $2 }
;
exp_list:
 | /*nothing*/ { [] }
 | exp exp_list_more { $1::$2 }
 ;
exp_list_more:
 | /*nothing*/ {[]}
 | COMMA exp exp_list_more { $2::$3 }
 ;
tag:
 | STRING { $1 }
 ;
With these pieces in place we can write the analyzer term_of_string like so
(*term.ml*)

let term_of_string s =
  let parse_buf lexbuf =
    try Parser.main Lexer.token lexbuf
    with 
    | Parsing.Parse_error ->
      begin
        let curr = lexbuf.Lexing.lex_curr_p in
        let line = curr.Lexing.pos_lnum in
        let cnum = curr.Lexing.pos_cnum - curr.Lexing.pos_bol in
        let tok = Lexing.lexeme lexbuf in
        raise 
          (Failure
             (Printf.sprintf 
                "file \"\", line %d, character %d\n\Error : Syntax error \"%s\"" line cnum tok))
      end
  in parse_buf (Lexing.from_string s)
Reverse parsing is done with string_of_term:
let rec string_of_term (t:(string, string)term) : string = 
  let string_of_list (f:α -> string) (l:α list) : string = 
    "(" ^ String.concat "," (List.map f l) ^ ")"  in
  match t with
  | Term (s, tl) -> Printf.sprintf "%s" (s^(string_of_list string_of_term tl))
  | Var s -> s
A simple function for printing a term then goes like this:
let print_term (t:(string, string) term) : unit = Printf.printf "%s" (string_of_term t)
For example, this program let tt = term_of_string "a(b(), c)" in print_term tt prints "a(b(), c)" recovering the input as we'd hope.

Traversal

The function term_trav is a workhorse for doing computations over terms. It generalizes all functions defined by recursion on the structure of a term.
(* [term_trav] is a generalization of all functions defined by
   recusion on the structure of an [(α, β) term] - a homomorphism.

   The definition of [term_trav] below gives the following signature.

   {[
   val term_trav : (α * β -> γ) ->
   (γ -> β -> β) -> β -> (δ -> γ) -> (α, δ) term -> γ
   ]}

   Proof:

   Assume [term_trav] to operate on arguments of type [(α, δ)
   term]. It "returns" either via [f] or [v], and so [f], [v] and
   [term_trav] must share the same return type, [γ] say.

   Since the intermediate list results from recursive calls to
   [term_trav] then it must have type [γ list]. This means [g] must
   be of type [γ -> β -> β] for some type [β] which fixes [x] to
   [β] whilst completing [f] as [α * β -> γ].

   Lastly [v] takes arguments of type [δ] meaning it types to [δ ->
   γ].

*)
let rec term_trav f g x v = function
  | Term (a, tl) -> 
    let l = List.map (term_trav f g x v) tl in
    let res = List.fold_right g l x in
    f (a, res)
  | Var b -> v b
For a trivial example, we can express a function to compute the "size" of a term this way:
let term_size (t:(α, β) term) : int = 
  (term_trav (fun (_, s) -> s + 1) (fun x y -> x + y) 0 (fun _ -> 1))
    t
I appreciate there's an efficiency gain to be had by eliminating the intermediate list in term_trav but the resulting function definition is more challenging to reason about (well, at least for me).

Saturday, September 21, 2013

Real world OCaml

Real world OCaml

For many tasks, I find OCaml as useful as Python and like "a better C".

This program matches files in a directory with a provided suffix and invokes a program on them.
(*e.g.
  Match files in directory with given suffix and invoke a program on
  them.

$ ./build/bin/filesin.exe -d \
    c:/project/examples -p \
    c:/project/someprog.exe
*)

(*Globals*)
let version,root,prog,suffix=ref false,ref "",ref "",ref ""

let (read_args:unit -> unit) = fun () ->
  let specification =
    [("-v", Arg.Set version, "Print the version number") ;
     ("-d", Arg.String (fun s -> root := s), "Directory") ;
     ("-s", Arg.String (fun s -> suffix := s), "Suffix") ;
     ("-p", Arg.String (fun s -> prog := s), "Path to the prog") ;
    ]
  in Arg.parse specification
  (fun s -> Printf.printf "Warning : Ignoring unrecognized argument \"%s\"\n" s)
  ("Usage : "^(Sys.argv.(0))^" options")

let (filesin:string -> string array option) = fun s ->
  if not (Sys.file_exists s)
       || not (Sys.is_directory s) then
    None
  else (Some (Sys.readdir s))

let (read_and_close:Unix.file_descr -> string)  = fun fdr ->
  let buf = Buffer.create 1024 in
  let bytes_to_read = ref true in
  while !bytes_to_read do
    let s  = String.create 1024 in
    let num_bytes_read = Unix.read fdr s 0 124 in
    Buffer.add_string buf (String.sub s 0 num_bytes_read) ;
    if num_bytes_read < 1024 then bytes_to_read := false ;
    ()
  done ;
  Unix.close fdr ;
  Buffer.contents buf

let (process_file:string -> unit) = fun f ->
  let p = Filename.concat (!root) f in
  let cmd = Printf.sprintf "%s -l -e %s" (!prog) p in
  (*I tried to use anonymous pipes here but that seems broken on
    Windows when [Unix.system] is involved*)
  let tf=Filename.temp_file "tmp" "" in
  let fdw = Unix.openfile tf [Unix.O_WRONLY; Unix.O_TRUNC; Unix.O_CREAT] 0o666 in
  let tmp = Unix.dup Unix.stdout in
  let stat = (
    Unix.dup2 fdw Unix.stdout ;
    Printf.printf "\n*** - %s:\n" p; flush stdout;
    Unix.system cmd  (*Invoke the intpreter on f*)
  )
  in
  Unix.dup2 tmp Unix.stdout ; Unix.close tmp; Unix.close fdw;
  match stat with
  | Unix.WEXITED 127 ->
    Printf.printf "The command \"%s\" could not be executed" cmd
  | _ ->
    let fdr = Unix.openfile tf [Unix.O_RDONLY] 0o666 in
    Printf.printf "%s" (read_and_close fdr) ; flush stdout (*; Sys.remove tf*)

let (process_files:string list -> unit) = fun fs ->
  List.iter (fun f -> process_file f) fs

let (main:unit) =
  read_args () ; Printf.printf "%s" !prog ;
  if !version then print_string "0.0.0\n"
  else
    if !suffix = "" then
    raise (Failure
      "Missing argument : suffix") ;
   if not (Sys.file_exists (!prog)) then
      raise (Failure (Printf.sprintf
        "Bad argument : The file '%s' does not exist" !prog)) ;
   try
     match (filesin !root) with
     | Some names ->
       let n=String.length !suffix in
       let pred e =
         let i = (String.length e - n) in
         (i >= 0) && (String.sub e i n) = !suffix
       in process_files (List.filter pred (Array.to_list names) )
     | None -> ()
   with
   | _  as e -> Printf.printf "Exception : %s\n" (Printexc.to_string e)

Friday, September 13, 2013

Sieve of Eratosthenes

Sieve of Eratosthenes

Find all the prime numbers less than or equal to k.

Python

import functools

k=1000

def sieve (k):

  def f (p, lst):
    s = list (filter (lambda i : i%p != 0 or i/p == 1, lst))
    r = list (filter (lambda i : i > p, s))
    if len (r) == 0:
        return s
    else:
        return f (r[0], s)

  return f (2, range (2, k + 1))

print (str(sieve (k)))

Sunday, September 8, 2013

Sub-arrays of maximal sum

Sub-arrays of maximal sum

Another puzzle problem from this blog. "You are given an array of n integers, each of which may be positive, negative or zero. Give an algorithm to identify the start and end index, i and j, of the interval whose elements form the maximal sum of all possible intervals. Assume j >=i. e.g. {1 3 -8 2 -1 10 -2 1} -> i=3, j=5 - sum=11.

Python

'''Find sub-arrays of maximal sum

   e.g. {1 3 -8 2 -1 10 -2 1} -> i=3, j=5 - sum=11

   http://basicalgos.blogspot.com/2012/05/52-find-sub-array-of-max-sum.html
'''

import functools

#Compute all the intervals of the sequence t per the definition
#above. e.g. for [1, 2, 3] compute [[1], [1, 2], [1, 2, 3], [2],
#[2, 3], [3]]. 
#Decorate the intervals with their start and end indices and the
#interval sum.
def intervals (t):
  def f (acc, i):
    def row (i, t):
      s = t[i:]
      def f (acc, j):
         indices=(i, i+j-1)
         interval=s[0:j]
         return acc + [(indices, interval, sum (interval, 0))]
      return functools.reduce (f, list (range (1, len (s) + 1)), [])
    return acc + row (i, t)
  return functools.reduce (f, list (range (0, len (t))), [])
  
#x, the input sequence.
x=[1, 3, -8, 2, -1, 10, -2, 1]

#Print the intervals of x with maximal sum.
res = intervals (x)
def f (m, t): 
  (_,_,n)=t ; return max (m, n)
maxsum = functools.reduce (f, res, 0)
for t in res:
  (indices, interval, total)=t
  if (total == maxsum):
    print (str(t)) #An interval of maximal sum.

C++

#include <vector>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <functional>

typedef std::pair<std::size_t, std::size_t> indicies_t;
inline std::size_t& fst (indicies_t& i) { return i.first; }
inline std::size_t& snd (indicies_t& i) { return i.second; }
inline std::size_t fst (indicies_t const& i) { return i.first; }
inline std::size_t snd (indicies_t const& i) { return i.second; }
void print_indicies (indicies_t const& p);

typedef std::vector<int> interval_t;
inline std::size_t len (interval_t const& i) { return i.size(); }
interval_t take (int k, interval_t const& lst);
interval_t drop (int k, interval_t const& lst);
inline int sum (interval_t const t)
{ 
  int tot=std::accumulate (t.begin(), t.end(), 0, std::plus<int>());

  return tot;
}
interval_t range (int begin, int end);
void print_interval (interval_t const& s);

struct interval_info_t
{
  indicies_t indicies; //(0, 2)
  interval_t interval; //e.g. [1, 2, 3]
  int total; //6
};
void print_interval_info (interval_info_t const& i);

typedef std::vector<interval_info_t> interval_info_set_t;

struct inner_f
{
  interval_t s;
  std::size_t i;

  inner_f (interval_t const& s, std::size_t i) 
    : s (s), i (i) 
  {}

  interval_info_set_t operator() 
  (interval_info_set_t acc, std::size_t j)
  {
    indicies_t indicies;
    fst (indicies) = i;
    snd (indicies) = i + j - 1;
    interval_t interval = take (j, s);
    int total = sum (interval);

    interval_info_t interval_info;
    interval_info.indicies = indicies;
    interval_info.interval = interval;
    interval_info.total = total;

    acc.push_back (interval_info);
  
    return acc;
 }
};

interval_info_set_t row (std::size_t i, interval_t const& t)
{
  interval_t s = drop (i, t);
  interval_t rg = range (1, len (s) + 1);
  
  return std::accumulate (
    rg.begin(), rg.end(), interval_info_set_t(), inner_f (s, i));
}

struct outer_f
{
  interval_t t;
  outer_f (interval_t const t) : t (t) {}

  interval_info_set_t operator() 
    (interval_info_set_t acc, std::size_t i) const
  {
    interval_info_set_t res=row (i, t);
    std::copy (res.begin(), res.end(), std::back_inserter (acc));
  
    return acc;
  }
};

interval_info_set_t intervals (interval_t const& t)
{
  interval_t rg = range (0, len (t));
  
  return std::accumulate (
    rg.begin(), rg.end(), interval_info_set_t (), outer_f (t));
}

inline int find_max (int m, interval_info_t const& t)
{
  return (std::max)(m, t.total);
}

//--driver

int main ()
{
  int data[] = {1, 3, -8, 2, -1, 10, -2, 1};
  interval_t input(data, data + sizeof(data)/sizeof(int));
  interval_info_set_t ivals = intervals (input);
  int maxsum = std::accumulate (ivals.begin(), ivals.end(), 0, find_max);

  for (std::size_t i = 0; i < ivals.size(); ++i)
    {
      if (ivals[i].total==maxsum)
 print_interval_info (ivals[i]); //An interval of maximal sum.
    }
  
  return 0;
}

//-- tools

interval_t take (int k, interval_t const& lst)
{
  if (k <= 0) return interval_t ();
  if (lst.size() == std::size_t (0)) return interval_t ();

  interval_t t = take (k-1, interval_t (++(lst.begin()), lst.end()));
  interval_t res (t.size()+1);
  res[0] = lst[0];
  for (std::size_t i = 0; i < len (t); ++i)
    res [i+1] = t[i];

  return res;
}

interval_t drop (int k, interval_t const& lst)
{
  if (k <= 0) return lst;
  if (lst.size () == 0) return interval_t ();

  return drop (k - 1, interval_t (++(lst.begin()), lst.end()));
}

interval_t range (int begin, int end)
{
  interval_t buf;
  for(int i = begin; i < end; ++i) buf.push_back (i);

  return buf;
}

void print_indicies (indicies_t const& p)
{
  std::cout << "(" << fst (p) << ", " << snd (p) << ")";
}

void print_interval (interval_t const& s)
{
  std::cout << "["; 
  std::ostream_iterator<int> out_it (std::cout, ", ");
  std::copy (s.begin(), s.end(), out_it);
  std::cout << "],"; 
}

void print_interval_info (interval_info_t const& i)
{
  std::cout << "(";
  print_indicies (i.indicies);
  print_interval (i.interval);
  std::cout << i.total;
  std::cout << ")\n";
}

Saturday, September 7, 2013

Permutations of a list

Permutations of a list

Find all the permutations of a list. For example, given the list [1,2, 3] compute all of [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1],[3, 1, 2], [3, 2, 1]].

The reasoning here goes like this. Suppose I know how to compute all the permutations of a list that start with the element at position k. Then the list of all permutations can be obtained by calling that function with k = 0, ..., N-1 where N is the length of the list. How do you compute the permutations of a list that start with the element at position k? Well, you compute all the permutations of the reduced list that doesn't contain the kth element and prepend them all with the kth element.

Python

def take(k, lst):
   '''The list slice, lst[0:k].
  
      >>> print (str(take(0, [1, 2, 3])))
      []
      >>> print (str(take(1, [1, 2, 3])))
      [1]
      >>> print (str(take(2, [1, 2, 3])))
      [1, 2]
      >>> print (str(take(3, [1, 2, 3])))
      [1, 2, 3]
      >>> print (str(take(4, [1, 2, 3])))
      [1, 2, 3]
  
   '''
   if(k <= 0):
       return []
   if(len(lst) == 0):
       return []
   return [lst[0]]+take(k-1, lst[1:])
  
def drop(k, lst):
    '''The list slice, lst[k:].
  
       >>> print (str(drop(0, [1, 2, 3])))
       [1, 2, 3]
       >>> print (str(drop(1, [1, 2, 3])))
       [2, 3]
       >>> print (str(drop(2, [1, 2, 3])))
       [3]
       >>> print (str(drop(3, [1, 2, 3])))
       []
       >>> print (str(drop(4, [1, 2, 3])))
       []
  
    '''
    if(k <= 0):
        return lst
    if(len(lst)==0):
        return []
    return drop(k-1, lst[1:])
  
def find_all_permutations(lst):
  '''Find all permutations of a list.
  
     >>> print (str(find_all_permutations([1, 2, 3])))
     [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
  
  '''
  def find_k_permutations(k, lst):
    '''Find all permutations of the given list that start with the
       element at index k.
  
    '''
    x = lst[k]
    listp=take(k, lst)+drop(k+1, lst)
    ps=find_all_permutations(listp)
    s = list (map (lambda perm : [x] + perm, ps))
 
    return s
  
  def loop(k, acc, lst):
      if(k == len(lst)):
          return acc
      else:
          return loop(k+1, acc + find_k_permutations(k, lst), lst)
  
  return ([[]], loop(0, [], lst))[len(lst)!=0]
  
if __name__ == "__main__":
    import doctest
    doctest.testmod()

C++

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>

typedef std::vector<int> perm_t;
typedef std::vector<int>::iterator perm_iterator_t;
typedef std::vector<int>::const_iterator perm_const_iterator_t;

typedef std::vector<perm_t> perm_set_t;
typedef std::vector<perm_t>::iterator perm_set_iterator_t;
typedef std::vector<perm_t>::const_iterator perm_set_const_iterator_t;

//-- print functions

void print_perm (perm_t const& s)
{
  std::cout << "["; 
  std::ostream_iterator<int> out_it (std::cout, ", ");
  std::copy (s.begin(), s.end(), out_it);
  std::cout << "],"; 
}

void print_perm_set (perm_set_t const& ts)
{
  std::cout << "[";
  perm_set_const_iterator_t begin=ts.begin (), end = ts.end ();
  perm_set_const_iterator_t t=begin;
  while (t != end)
    {
      print_perm (*t);
      ++t;
    }
  std::cout << "]";
}

//-- take, drop

perm_t take (int k, perm_t const& lst)
{
  if (k <= 0)
    {
      return perm_t ();
    }
  if (lst.size() == std::size_t (0))
    {
      return perm_t ();
    }

  perm_t t = take (k-1, perm_t (++(lst.begin()), lst.end()));
  perm_t res (t.size()+1);
  res[0] = lst[0];
  for (std::size_t i = 0; i < t.size (); ++i)
    res [i+1] = t[i];

  return res;
}

perm_t drop (int k, perm_t const& lst)
{
  if (k <= 0)
    {
      return lst;
    }

  if (lst.size () == 0)
    {
      return perm_t ();
    }

  return drop (k - 1, perm_t (++(lst.begin()), lst.end()));
}

//-- helpers

perm_set_t find_all_permutations (perm_t const& lst);

//Prepend x to a perm.

struct prepend
{
  int x;

  prepend (int x) : x (x)
  {}

  perm_t operator ()(perm_t const& p) const
  {
    perm_t r (p.size() + 1);
    r[0] = x;
    for (std::size_t i = 0; i < p.size(); ++i)
      r[i + 1] = p[i];

    return r;
  }
};

//Find all permutations of the given list that
//start with the element at index k.

perm_set_t find_k_permutations (int k, perm_t const& lst)
{
  int x = lst[k];
  perm_t left = take (k, lst);
  perm_t right = drop (k + 1, lst);
  perm_t listp;
  std::copy (left.begin(), left.end(), std::back_inserter (listp));
  std::copy (right.begin(), right.end(), std::back_inserter (listp));
  perm_set_t ps = find_all_permutations (listp);
  perm_set_t s;
  std::transform (ps.begin(), ps.end(), std::back_inserter(s), prepend (x));

  return s;
}

perm_set_t loop (int k, perm_set_t acc, perm_t lst)
{
  if (k == lst.size())
    return acc;
  else
    {
      perm_set_t t = find_k_permutations (k, lst);
      std::copy (t.begin (), t.end (), std::back_inserter (acc));
      
      return loop (k+1, acc, lst);
    }
}

perm_set_t find_all_permutations (perm_t const& lst)
{
  if (lst.size() == 0)
    {
      perm_set_t res;
      res.push_back (perm_t ());//The empty sequence.

      return res;
    }

  return loop (0, perm_set_t (), lst);
}

//-- test

int main()
{
  int data[] = {1, 2, 3};
  perm_t input (data, data + sizeof(data)/sizeof(int));

  print_perm_set (find_all_permutations (input));

  return 0;
}

Longest increasing sub-sequence

Longest increasing sub-sequence


According to this blog, "The longest increasing sub-sequence problem is to find a sub-sequence of a given sequence in which the sub-sequence elements are in sorted order, lowest to highest, and in which the sub-sequence is as long as possible". As an example, for 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 they give one longest increasing sub-sequence as 0, 2, 6, 9, 13, 15.

Python

'''Find a longest increasing subsequence
http://basicalgos.blogspot.com/2012/03/37-longest-increasing-sequence-lis.html

'''
import functools

def ics (s):  #s is s sequence
  """Find the set of increasing subsequences of s.

  """
  if len (s) == 1 :
      return [s] #s itself is an ics of length 1

  #This is the key point.
  ts = ics (s[1:]) #ts are the ics values of s - it's first element

  #Extend ts with any new subsequences that can be formed by
  #prepending s[0] to t for t in ts.
  def f (acc, t) :
    if s[0] < t[0]:
       nt = [s[0]]+t
       return acc + [nt]
    else:
        return acc
  res = functools.reduce (f, ts, ts) + [[s[0]]]

  return res

#s, the input sequence.

s=[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

#Print all longest increasing subsequences of s.

res = ics (s) #Find every ics of s
lens=list (map (lambda x : len (x), res)) #Now their lengths
lismax= \
  functools.reduce (\
    lambda acc, y: max (acc, y), lens, 0) #The max length
for f in res:
    if len(f) == lismax: print (str(f)) #An ics of max length

C++

/*
Find a longest increasing subsequence
http://basicalgos.blogspot.com/2012/03/37-longest-increasing-sequence-lis.html
 */
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <numeric>

typedef std::vector<int> ics_t;
typedef ics_t::const_iterator ics_const_iterator_t;
typedef ics_t::iterator ics_iterator_t;

typedef std::vector<ics_t> ics_set_t;
typedef ics_set_t::const_iterator ics_set_const_iterator_t;
typedef ics_set_t::iterator ics_set_iterator_t;

//-- print functions

void print_ics (ics_t const& s)
{
  std::cout << "["; 
  std::ostream_iterator<int> out_it (std::cout, ", ");
  std::copy (s.begin(), s.end(), out_it);
  std::cout << "],"; 
}

void print_ics_set (ics_set_t const& ts)
{
  std::cout << "[";
  ics_set_const_iterator_t begin=ts.begin (), end = ts.end ();
  ics_set_const_iterator_t t=begin;
  while (t != end)
    {
      print_ics (*t);
      ++t;
    }
  std::cout << "]";
}

//-- Calculate the length of an ics

std::size_t len_ics (ics_t const& s)
{
  return s.size ();
}

//-- Calculate the max ics length in a set

std::size_t max_ics_len (ics_set_t const& s)
{
  std::vector<std::size_t> lens;
  std::transform (
    s.begin (), s.end (), std::back_inserter (lens), len_ics);

  return std::accumulate (
        lens.begin (), lens.end (), 0, std::max<std::size_t>);
}

//  Extend ts with any new subsequences that can be formed by
//  prepending s[0] to t for t in ts.

struct f // f : ics_set_t * ics_t -> ics_set_t
{
  int s0; 

  f (int s0) : s0 (s0) 
  {}
  ics_set_t operator()(ics_set_t acc, ics_t const& t) const
  {
    if (s0 < t[0])
      {
        ics_t nt (t.size() + 1);
        nt[0] = s0;
        for (std::size_t i=0; i < t.size(); ++i)
          nt[i+1] = t[i];
        acc.push_back (nt);

        return acc;
      }
    else
      {
        return acc;
      }
  }
};

//Find the set of increasing subsequences of s.
ics_set_t ics (ics_t s)
{
  if (s.size () == 1)
    {
      ics_set_t res;
      res.push_back (s); //s itself is an ics of length 1

      return res;
    }

  //This is the key point.
  ics_set_t ts = ics (ics_t(++(s.begin()), s.end())); 
  //ts are the ics values of s - it's first element

  //Extend ts with any new subsequences that can be formed by
  //prepending s[0] to t for t in ts.
  ics_set_t t=std::accumulate (ts.begin (), ts.end(), ts, f(s[0]));
  t.push_back (ics_t(1, s[0]));

  return t;
}

int main ()
{
  int data[] = 
  {
    0, 8, 4, 12, 2, 10, 6, 14, 1,9, 5, 13, 3, 11, 7, 15
  };
  ics_t s (data, data + sizeof(data)/sizeof(int));

  ics_set_t res = ics (s);
  std::size_t n=max_ics_len (res);
  for (std::size_t i = 0; i < res.size (); ++i)
    {
      ics_t const& x=res[i];
      if (x.size () == n)
      {
        print_ics (x);
        std::cout << std::endl;
      }
    }
  
  return 0;
}