基于模板生成所有字符串组合

Question

如何基于模板生成所有字符串组合？

例如： - 模板字符串为

"{I|我们}想要{|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]]

- kanggary

---

这是编程语言的任务，而不仅仅是正则表达式。 - revo

谷歌一下。正则表达式不适用。听起来像是嵌套循环。 - user557597

以上正则表达式可以保存为有限树，深度优先搜索可得到所有可能的字符串。 - user2314737

在循环中，C 伪代码类似于 pI[] = {'I','We'}; pJ[] = {'' ,'2','3','4'}; pK[] = {'apples','pears'}; for ( i = 0; i < 2; i++ ) { string strI = pI[i]; strI += 'want'; for ( j = 0; j < 4; j++ ) { strJ = strI + pJ[j]; for ( k = 0; k < 2; k++ ) { strK = strJ + pK[k]; print( strK ); } } } - user557597

@sln模板是输入的（不是常量，这只是一个例子）。 - kanggary

它可以推广到可变输入。我的代码只是一个例子。这只是普通的循环，做同样的事情，只是参数不同。它可以是递归的。 - user557597

Answer 1

到目前为止，我发现解决这个问题最实用的方法是使用 Python 模块 sre_yield。

sre_yield 的目标是高效地生成与给定正则表达式匹配的所有值，或者高效地计算可能的匹配次数。

_{强调是我添加的。}

要将其应用于您所述的问题：将您的模板公式化为正则表达式模式，并在 sre_yield 中使用它来获取所有可能的组合或计算可能的匹配次数，如下所示：

import sre_yield
result = set(sre_yield.AllStrings("(I|We) want (|2|3|4) (apples|pears)"))
result.__len__()
result

输出：

16
{'I want  apples',
 'I want  pears',
 'I want 2 apples',
 'I want 2 pears',
 'I want 3 apples',
 'I want 3 pears',
 'I want 4 apples',
 'I want 4 pears',
 'We want  apples',
 'We want  pears',
 'We want 2 apples',
 'We want 2 pears',
 'We want 3 apples',
 'We want 3 pears',
 'We want 4 apples',
 'We want 4 pears'}

提示：与项目页面上显示的列表不同，我使用集合来避免重复。如果这不是您想要的，请选择列表。

- wp78de

Answer 2

Shell通配符

$ for q in {I,We}\ want\ {2,3,4}\ {apples,pears}; do echo "$q" ; done
I want 2 apples
I want 2 pears
I want 3 apples
I want 3 pears
I want 4 apples
I want 4 pears
We want 2 apples
We want 2 pears
We want 3 apples
We want 3 pears
We want 4 apples
We want 4 pears

- ikegami

Answer 3

原则是：

• 正则表达式 -> NFA
• NFA -> 最小化DFA
• DFS-遍历DFA（收集所有字符）

例如，在RexLex中实现了这个原则：

DeterministicAutomaton dfa = Pattern.compileGenericAutomaton("(I|We) want (2|3|4)? (apples|pears)")
  .toAutomaton(new FromGenericAutomaton.ToMinimalDeterministicAutomaton());
if (dfa.getProperty().isAcyclic()) {
  for (String s : dfa.getSamples(1000)) {
    System.out.println(s);
  }
}

- CoronA

Answer 4

将每组字符串 {...} 转换为 字符串数组，以便您有 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);
        }
    }

*更正编辑

- Joseph Franciscus

---

抱歉，格式可能有些问题。如果你需要索引，你可以生成另一个String[]，将当前索引[y]作为特定单词添加进去。 - Joseph Franciscus