How to create all possible variations from single string presented in special format?

Question

Let's say, I have following template.

Hello, {I'm|he is} a {notable|famous} person.

Result should be

Hello, I'm a notable person.
Hello, I'm a famous person.
Hello, he is a notable person.
Hello, he is a famous person.

The only possible solution I have in mind - full search, but it is not effective. May be there is a good algorithm for such kind of job but I do not know what task about. All permutations in array is very close to this but I have no idea how to use it here.

Here is working solution (it's part of object, so here is only relevant part).

generateText() parses string and converts 'Hello, {1|2}, here {3,4}' into ['Hello', ['1', '2'], 'here', ['3', '4']]]

extractText() takes this multidimensional array and creates all possible strings

        STATE_TEXT: 'TEXT',
        STATE_INSIDE_BRACKETS: 'INSIDE_BRACKETS',

        generateText: function(text) {
            var result = [];
            var state = this.STATE_TEXT;
            var length = text.length;
            var simpleText = '';
            var options = [];
            var singleOption = '';
            var i = 0;

            while (i < length) {
                var symbol = text[i];

                switch(symbol) {
                    case '{':
                        if (state === this.STATE_TEXT) {
                            simpleText = simpleText.trim();
                            if (simpleText.length) {
                                result.push(simpleText);
                                simpleText = '';
                            }
                            state = this.STATE_INSIDE_BRACKETS;
                        }
                        break;
                    case '}':
                        if (state === this.STATE_INSIDE_BRACKETS) {
                            singleOption = singleOption.trim();
                            if (singleOption.length) {
                                options.push(singleOption);
                                singleOption = '';
                            }
                            if (options.length) {
                                result.push(options);
                                options = [];
                            }
                            state = this.STATE_TEXT;
                        }
                        break;
                    case '|':
                        if (state === this.STATE_INSIDE_BRACKETS) {
                            singleOption = singleOption.trim();
                            if (singleOption.length) {
                                options.push(singleOption);
                                singleOption = '';
                            }
                        }
                        break;
                    default:
                        if (state === this.STATE_TEXT) {
                            simpleText += symbol;
                        } else if (state === this.STATE_INSIDE_BRACKETS) {
                            singleOption += symbol;
                        }
                        break;
                }

                i++;
            }

            return result;
        },

        extractStrings(generated) {
            var lengths = {};
            var currents = {};
            var permutations = 0;
            var length = generated.length;
            for (var i = 0; i < length; i++) {
                if ($.isArray(generated[i])) {
                    lengths[i] = generated[i].length;
                    currents[i] = lengths[i];
                    permutations += lengths[i];
                }
            }

            var strings = [];

            for (var i = 0; i < permutations; i++) {
                var string = [];
                for (var k = 0; k < length; k++) {
                    if (typeof lengths[k] === 'undefined') {
                        string.push(generated[k]);
                        continue;
                    }

                    currents[k] -= 1;
                    if (currents[k] < 0) {
                        currents[k] = lengths[k] - 1;
                    }
                    string.push(generated[k][currents[k]]);
                }

                strings.push(string.join(' '));
            }

            return strings;
        },

Answer 1

The only possible solution I have in mind - full search, but it is not effective.

If you must provide full results, you must run full search. There is simply no way around it. You don't need all permutations, though: the number of results is equal to the product of the number of alternatives in each template.

Although there are multiple ways to implement this, recursion is among the most popular approaches. Here is some pseudo-code to get you started:

string[][] templates = {{"I'm", "he is"}, {"notable", "famous", "boring"}}
int[] pos = new int[templates.Length]
string[] fills = new string[templates.Length]
recurse(templates, fills, 0)
...
void recurse(string[][] templates, string[] fills, int pos) {
    if (pos == fills.Length) {
        formatResult(fills);
    } else {
        foreach option in templates[pos] {
            fills[pos] = option
            recurse(templates, fills, pos+1);
        } 
    }
}

Answer 2

It seems like the best solution here is going to be n*m where n=the first array and m= the second array . There are nm required lines of output, which means that as long as you are only doing nm you aren't doing any extra work

The generic running time for this is where there is more than 2 arrays with options, it would be

n₁*n₂...*n_m where each of those is equal to the size of the respective list

A nested loop where you just print out the value for the current index of the outer loop along with the current value for the index of the inner loop should do this properly