根据模板生成所有字符串组合

Question

如何根据模板生成所有字符串组合？

例如： - 模板字符串

“{我|我们}想要{|2|3|4} {苹果|梨}”

大括号“{...}”标识一组或多个单词，每个单词用“|”分隔。

该类应使用每个单词组中的每种单词组合生成字符串。

我知道它是有限自动机，也是正则表达式。如何高效生成组合？

例如

G[0][j] [想要] G[1][j] G[2][j]"

G[0] = {I, We}
G[1] = {2, 3, 4}
G[2] = {apples, pears}

首先，生成所有可能的组合 c = [0..1][0..2][0..1]：

000
001
010
011
020
021
100
101
110
111
120    
121

然后对于每个 c 将 G[i][j] 替换为 G[i][c[i]]

Answer 1

将每组字符串 {...} 转换为 a string array，这样就有 n 个数组。所以"{I|We} want {|2|3|4} {apples|pears}"我们会有 4 个数组。

将每个数组放入另一个数组中。在我的示例中，我将调用collection

这是 Java 代码，但它足够简单，您应该能够将其转换为任何语言。我没有测试，但它应该可以工作。

void makeStrings(String[][] wordSet, ArrayList<String> collection) {
       makeStrings(wordSet, collection, "", 0, 0);
}

void makeStrings(String[][] wordSet, ArrayList<String> collection, String currString, int x_pos, int y_pos) {

    //If there are no more wordsets in the whole set add the string (this means 1 combination is completed)
    if (x_pos >= wordSet.length) {
        collection.add(currString);
        return; 
    }


        //Else if y_pos is outof bounds (meaning no more words within the smaller set {...} return
    else if (y_pos >= wordSet[x_pos].length) { 
        return;
    } 



    else {
            //Generate 2 new strings, one to send "vertically " and one "horizontally"
            //This string accepts the current word at x.y and then moves to the next word subset
            String combo_x = currString + " " + wordSet[x_pos][y_pos];
            makeStrings(wordSet, collection, combo_x, x_pos + 1, 0);

            //Create a copy of the string and move to the next string within the same subset
            String combo_y = currString;
            makeStrings(wordSet, collection, combo_y, x_pos , y_pos  + 1);
        }
    }

*编辑更正