How to resolve the algorithm Non-continuous subsequences step by step in the ALGOL 68 programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Non-continuous subsequences step by step in the ALGOL 68 programming language

Table of Contents

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:

Step by Step solution about How to resolve the algorithm Non-continuous subsequences step by step in the ALGOL 68 programming language

Source code in the algol programming language

PROC test non continuous = VOID: BEGIN
   MODE SEQMODE = CHAR;
   MODE SEQ = [1:0]SEQMODE;
   MODE YIELDSEQ = PROC(SEQ)VOID;

   PROC gen ncs =
             (  SEQ tail,       # To generate subsequences of #
                SEQ head,       #           Already generated #
                BOOL contiguous,#      It is still continuous #
                YIELDSEQ yield
             )  VOID:
   BEGIN
      IF NOT contiguous ANDTH UPB head > 1 THEN
         yield (head)
      FI;
      IF UPB tail /= 0 THEN 
            [UPB head+1]SEQMODE new head;
            new head [:UPB head] := head;
            FOR i TO UPB tail DO
               new head [UPB new head] := tail [i];
               gen ncs
               (  tail[i + 1:UPB tail],
                  new head,
                  contiguous ANDTH (i = LWB tail OREL UPB head = 0),
                  yield
               )
            OD
      FI
   END # put ncs #;

 # FOR SEQ seq IN # gen ncs(("a","e","i","o","u"), (), TRUE, # ) DO ( #
 ##   (SEQ seq)VOID:
      print((seq, new line))
 # OD # )
END; test non continuous

MODE SEQMODE = STRING;
MODE SEQ = [1:0]SEQMODE;
MODE YIELDSEQ = PROC(SEQ)VOID;

PROC gen ncs = (SEQ seq, YIELDSEQ yield)VOID:
BEGIN
  IF UPB seq - 1 > bits width THEN stop FI;
  [UPB seq]SEQMODE out;  INT upb out;

  BITS lim := 16r1 SHL UPB seq;
  BITS upb k := lim SHR 1;
  # assert(lim); #

  BITS empty = 16r000000000; # const #

  FOR j TO ABS lim-1 DO
    INT state := 1;
    BITS k1 := upb k; 
    WHILE k1 NE empty DO
      BITS b := BIN j AND k1;
      CASE state IN
        # state 1 # IF b NE empty THEN state +:= 1 FI,
        # state 2 # IF b EQ empty THEN state +:= 1 FI,
        # state 3 # 
          BEGIN
            IF b EQ empty THEN GO TO continue k1 FI;
            upb out := 0; 
            BITS k2 := upb k; FOR i WHILE k2 NE empty DO
              IF (BIN j AND k2) NE empty THEN out[upb out +:= 1] := seq[i] FI;
              k2 := k2 SHR 1
            OD;
            yield(out[:upb out]);
            k1 := empty # empty: ending containing loop #
         END
      ESAC;
      continue k1: k1 := k1 SHR 1
    OD
  OD
END;

main:(
  []STRING seqs = ("a","e","i","o","u");
# FOR SEQ seq IN # gen ncs(seqs, # ) DO ( #
##   (SEQ seq)VOID:
    print((seq, new line))
# OD # )
)

  

You may also check:How to resolve the algorithm Count in factors step by step in the C++ programming language
You may also check:How to resolve the algorithm Permutations by swapping step by step in the Haskell programming language
You may also check:How to resolve the algorithm Sort an outline at every level step by step in the Python programming language
You may also check:How to resolve the algorithm Check output device is a terminal step by step in the Standard ML programming language
You may also check:How to resolve the algorithm Assertions step by step in the Z80 Assembly programming language