lyrically wicked - 6 months ago 35

Javascript Question

I have a string

`str`

`M`

`N`

`M`

`N`

`N`

`M`

`M`

`N`

`N`

`M=1`

`N=3`

`"aabcde"`

`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"]
```