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

Published on 12 May 2024 09:40 PM
#D

How to resolve the algorithm Non-continuous subsequences step by step in the D 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 D programming language

Source code in the d programming language

T[][] ncsub(T)(in T[] seq, in uint s=0) pure nothrow @safe {
    if (seq.length) {
        typeof(return) aux;
        foreach (ys; ncsub(seq[1 .. $], s + !(s % 2)))
            aux ~= seq[0] ~ ys;
        return aux ~ ncsub(seq[1 .. $], s + s % 2);
    } else
        return new typeof(return)(s >= 3, 0);
}

void main() @safe {
    import std.stdio;

    [1, 2, 3].ncsub.writeln;
    [1, 2, 3, 4].ncsub.writeln;
    foreach (const nc; [1, 2, 3, 4, 5].ncsub)
        nc.writeln;
}


struct Ncsub(T) {
    T[] seq;

    int opApply(int delegate(ref T[]) dg) const {
        immutable n = seq.length;
        int result;
        auto S = new T[n];

        OUTER: foreach (immutable i; 1 .. 1 << n) {
            uint lenS;
            bool nc = false;
            foreach (immutable j; 0 .. n + 1) {
                immutable k = i >> j;
                if (k == 0) {
                    if (nc) {
                        auto auxS = S[0 .. lenS];
                        result = dg(auxS);
                        if (result)
                            break OUTER;
                    }
                    break;
                } else if (k % 2) {
                    S[lenS] = seq[j];
                    lenS++;
                } else if (lenS)
                    nc = true;
            }
        }

        return result;
    }
}

void main() {
    import std.array, std.range;

    //assert(24.iota.array.Ncsub!int.walkLength == 16_776_915);
    auto r = 24.iota.array;
    uint counter = 0;
    foreach (s; Ncsub!int(r))
        counter++;
    assert(counter == 16_776_915);
}


import std.stdio, std.array, std.range, std.concurrency;

Generator!(T[]) ncsub(T)(in T[] seq) {
    return new typeof(return)({
        immutable n = seq.length;
        auto S = new T[n];

        foreach (immutable i; 1 .. 1 << n) {
            uint lenS = 0;
            bool nc = false;
            foreach (immutable j; 0 .. n + 1) {
                immutable k = i >> j;
                if (k == 0) {
                    if (nc)
                        yield(S[0 .. lenS]);
                    break;
                } else if (k % 2) {
                    S[lenS] = seq[j];
                    lenS++;
                } else if (lenS)
                    nc = true;
            }
        }
    });
}

void main() {
    assert(24.iota.array.ncsub.walkLength == 16_776_915);

    [1, 2, 3].ncsub.writeln;
    [1, 2, 3, 4].ncsub.writeln;
    foreach (const nc; [1, 2, 3, 4, 5].ncsub)
        nc.writeln;
}

You may also check:How to resolve the algorithm Topswops step by step in the Elixir programming language
You may also check:How to resolve the algorithm RPG attributes generator step by step in the Action! programming language
You may also check:How to resolve the algorithm Write entire file step by step in the Tcl programming language
You may also check:How to resolve the algorithm Thue-Morse step by step in the PicoLisp programming language
You may also check:How to resolve the algorithm Safe primes and unsafe primes step by step in the Smalltalk programming language