lyrically wicked lyrically wicked - 17 days ago 4
Javascript Question

Given a string, how to generate all possible arrays of substrings where each substring contains no more than N, but not less than M chars?

I have a string

str
and two positive integers,
M
and
N
, where
M
can be less than or equal to
N
. All I want is to split the string so that each part contains no more than
N
chars, but not less than
M
chars (assuming that the length of the string is greater than
M
; if it is not greater than
N
, we may assume that
N
is equal to the length of the string). For example, if
M=1
,
N=3
and my string is
"aabcde"
, the result should be

var str = "aabcde";
var result = [
["a", "a", "b", "cde"],
["a", "ab", "cde"],
["aa", "b", "cde"],
//...
["aab", "cde"],
["aab", "cd", "e"],
["aab", "c", "de"],
["aab", "c", "d", "e"]
]


What is the efficient way to solve this, avoiding unnecessary intermediate subarrays? I don't want to generate all possible combinations, and then delete each subarray if it contains at least one substring with inacceptable length. Is there another way, without unnecessary computations?

Answer

This effectively boils down to generating restricted integer compositions with parts between two values M and N. It is a simple matter to generate such compositions recursively.

I also noticed in your example for "aabcde", M=1, N=3" that your array lengths were all less than or equal to 4 in length, so I also included an optional parameter to restrict the number of parts in each composition.

function* restrictedCompositions(n, a, b, k = n) {
    if (!(0 < a && a <= b && b <= n && 0 < k && k <= n)) {
        throw "invalid arguments";
    }

    let C = [];

    function* recGen(m, r) {
        if (m == 0) {
            yield C; // client must copy if they wish to store value for later
        }
        else {
            let y = Math.min(b, m);
            let x = Math.max(a, m - y*(r - 1));

            for (let v = x; v <= y; v++) {
                C.push(v);
                yield* recGen(m - v, r - 1);
                C.pop();
            }
        }   
    }

    yield* recGen(n, k);
}

function* generateChoppedStrings(str, M, N, K = str.length) {
    for (let composition of restrictedCompositions(str.length, M, N, K)) {
        let chopped = [];
        let i = 0;

        for (let part of composition) {
            let j = i + part;
            chopped.push(str.slice(i, j));
            i = j;
        }

        yield chopped;
    }
}

function chopString(str, M, N, K = str.length) {
    for (let chopped of generateChoppedStrings(str, M, N, K)) {
        console.log(chopped);
    }
}

chopString("aabcde", 1, 3, 4);

Output:

["a", "a", "b", "cde"]
["a", "a", "bc", "de"]
["a", "a", "bcd", "e"]
["a", "ab", "c", "de"]
["a", "ab", "cd", "e"]
["a", "ab", "cde"]
["a", "abc", "d", "e"]
["a", "abc", "de"]
["aa", "b", "c", "de"]
["aa", "b", "cd", "e"]
["aa", "b", "cde"]
["aa", "bc", "d", "e"]
["aa", "bc", "de"]
["aa", "bcd", "e"]
["aab", "c", "d", "e"]
["aab", "c", "de"]
["aab", "cd", "e"]
["aab", "cde"]