java - 生成短语排列

Question

我有一个有趣的问题，但我终其一生都无法找到一个好的解决方案。我将得到一个包含 0+ 个“标记”的短语。例如:

How now %A1% cow. The %A2% had oddly-shaped %A3%.

以上，%A1%、%A2%和%A3%都是“token”。每个标记都有其各自的可能单词列表，可以用来代替它:

public class Token {
    // Ex: %A1%
    private String code;

    // Ex: "brown", "red", "silly"
    private List<String> candidates;
}

我需要编写一些代码来获取任意短语(不仅仅是上面的示例)并扫描它以查找标记的存在。如果找到标记，那么我需要它使用每个标记的候选列表的每个组合来生成短语的每个排列。例如，如果上述 3 个 token 存在以下候选者:

%A1%
====
brown
red
silly

%A2%
====
arsonist
banker

%A3%
====
feet
hands

然后将生成以下句子排列:

How now brown cow. The arsonist had oddly-shaped feet.
How now brown cow. The arsonist had oddly-shaped hands.
How now brown cow. The banker had oddly-shaped feet.
How now brown cow. The banker had oddly-shaped hands.
How now red cow. The arsonist had oddly-shaped feet.
How now red cow. The arsonist had oddly-shaped hands.
How now red cow. The banker had oddly-shaped feet.
How now red cow. The banker had oddly-shaped hands.
How now silly cow. The arsonist had oddly-shaped feet.
How now silly cow. The arsonist had oddly-shaped hands.
How now silly cow. The banker had oddly-shaped feet.
How now silly cow. The banker had oddly-shaped hands.

因为 %A1% 有 3 个可能的值，而 %A2% 和 %A3% 都有 2 个可能的值，我们有总共 3 x 2 x 2 = 12 个排列。

如果我们在短语中始终有固定数量的标记，那么问题就容易多了(至少对我而言)。但问题是:

1. 我们不确定该短语将包含多少个标记(它甚至可能包含 0 个标记)；和
2. 我们不知道每个短语中会出现什么标记(以及哪些候选列表)，因此我们需要扫描短语并获取标记列表，然后能够动态地将它们放入“排列”发电机”根据需要。

出于某种原因，我无法全神贯注于此。关于如何编写代码的任何想法？提前致谢!

Answer 1

您可以使用递归函数来获取所有排列。像这样的伪代码:

void applyAllTokens(string s, stack<string> token_names) {
     if (token_names.isEmpty()) { 
         print(s);
         return;
     }
     top_name = token_names.pop();
     foreach (string token_value in map[top_name]) {
         string t = replaceToken(s,top_name,token_value);
         applyAllTokens(t,token_names.copy());
     }
}