All substrings of a string, without shuffling-CodePudding

I've looked into Heap's algorithm for generating permutations, and all the numerous results on here for similar questions.

But they all seem to want every permutation where the input can be shuffled around as much as it wants to be.

I'd like a function that returns all possible substrings where the order remains the same so for input "abc" the result should not include "cba" for instance.

Here's what I mean:

getAllSubstrings("abcdefg") should return:

[
"a","b","c","d","e","f","g"
"ab","cd","ef",                   //"g"
"bc","de","fg",                   //"a"
"abc","def",                      //"g"
"bcd","efg",                      //"a"
"cde",                            //"fg", "ab"
"abcd",                           //"efg"
"bcde",                           //"a","fg"
"cdef",                           //"ab", "g"
"defg",                           //"abc"
"abcde",                          //"fg"
"bcdef",                          //"a""g"
"cdefg",                          //"ab"
"abcdefg"
]

Using Set to throw away the duplicate values is perfectly fine. I just can't wrap my head around how you would achieve the above. And it seems pretty simple...

Anyone got any good ideas for how one can achieve this?

CodePudding user response：

Here is how you could do it with a generator:

function* getAllSubstrings(s) {
    for (let len = 1; len <= s.length; len  ) {
        for (let i = 0; i   len <= s.length; i  ) {
            yield s.slice(i, i   len);
        }
    }
}

console.log(Array.from(getAllSubstrings("abcedfg")));

Or as a traditional function:

function getAllSubstrings(s) {
    const result = [];
    for (let len = 1; len <= s.length; len  ) {
        for (let i = 0; i   len <= s.length; i  ) {
            result.push(s.slice(i, i   len));
        }
    }
    return result;
}

console.log(getAllSubstrings("abcedfg"));

Or in a functional style:

const getAllSubstrings = s =>
    Array.from(s, (_, k) =>
        Array.from(s.slice(k), (_, i) =>
            s.slice(i, i   k   1)
        )
    ).flat();

console.log(getAllSubstrings("abcedfg"));

CodePudding user response：

A slightly different approach with a different oder of the result set.

function* getAllSubstrings(s) {
    for (let i = 1; i < s.length; i  ) yield s.slice(0, i);
    if (s.length === 1) return;
    yield* getAllSubstrings(s.slice(1));
}

console.log(Array.from(getAllSubstrings("abcedfg")));

.as-console-wrapper { max-height: 100% !important; top: 0; }