Problem Statement

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.

For the sequence   1,2,3,4,   there are five non-continuous subsequences, namely:

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

Let's start with the solution:

$ include "seed7_05.s7i";

const func array bitset: ncsub (in bitset: seq, in integer: s) is func
  result
    var array bitset: subseq is 0 times {};
  local
    var bitset: x is {};
    var bitset: xs is {};
    var bitset: ys is {};
  begin
    if seq <> {} then
      x := {min(seq)};
      xs := seq - x;
      for ys range ncsub(xs, s + 1 - s rem 2) do
        subseq &:= x | ys;
      end for;
      subseq &:= ncsub(xs, s + s rem 2);
    elsif s >= 3 then
      subseq &:= {};
    end if;
  end func;

const proc: main is func
  local
    var bitset: seq is {};
  begin
    for seq range ncsub({1, 2, 3, 4}, 0) do
      writeln(seq);
    end for;
  end func;