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:

# Generate a stream of subsets of the input array
def subsets:
  if length == 0 then []
  else .[0] as $first
    | (.[1:] | subsets) 
    | ., ([$first] + .)
  end ;

# Generate a stream of non-continuous indices in the range 0 <= i < .
def non_continuous_indices:
  [range(0;.)] | subsets
  | select(length > 1 and length != 1 + .[length-1] - .[0]) ;

def non_continuous_subsequences:
  (length | non_continuous_indices) as $ix
  | [.[ $ix[] ]] ;

def count(f): reduce f as $i (0; . + 1);

count( [range(0;20)] | non_continuous_subsequences)