1

我有一个有趣的问题，我无法 - 为了我的生活 - 找出一个好的解决方案。我将得到一个包含 0+ 个“标记”的短语。例如：

现在 %A1% 牛怎么样。%A2% 的 %A3% 形状奇特。

上面，%A1%和%A2%都是%A3%“标记”。每个标记都有自己的可能单词列表，可以用来代替它：

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

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

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

%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.

因为有 3 个可能的值，并且%A1%两者都有 2 个可能的值，所以我们总共有 3 x 2 x 2 = 12 个排列。%A2%%A3%

如果我们在短语中总是有固定数量的标记，那么问题就容易多了（至少对我来说）。但问题是：

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

出于某种原因，我无法将我的大脑包裹在这个周围。关于如何编码的任何想法？提前致谢！

4

3 回答 3

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());
     }
}
于 2013-10-23T21:25:51.987 回答
0

您扫描该短语并获得ListL 个令牌 TokenList。列表的每个元素都映射到List该令牌的候选对象 TokenList[i]，其中 i 在 [0,L) 中：

TokenList[0] = [ Cow, Fox, Dog ]
TokenList[1] = [ Rapist, Arsonist, Murderer, Rapist ]
TokenList[2] = [ Feet, Shoulders, Knees, Toes ]
...

现在您需要一个函数，该函数将获取候选实例列表 - 例如 [ Cow, Arsonist, Feet ] - 和具有该数量标记的短语，并替换标记。

您的问题现在变成了如何从列表列表中生成所有实例列表。如另一个答案中所述，您可以递归地执行此操作。

对于小于平台上最大整数值的数字，您可以迭代地执行此操作。首先计算迭代次数：它将是所有 L 个列表的大小 N 的乘积。

现在，

for (i = 0; i < N; i++) {
    R = i
    Tokens = [ ]
    for (j = 0; j < L; j++) {
        Tokens[j] = TokenList[ R % TokenList[j].length ]
        R /= TokenList[j].length
    }
    generateSentence(template, Tokens)
}

将按顺序生成所有组合。

于 2013-10-23T21:47:07.810 回答
-1

在我回家之前只是一个粗略的轮廓......

假设您的输入短语%除了使用标记外不包含，您可以只split()在%符号上使用。结果数组将在令牌和非令牌之间交替。通过这种方式，您可以轻松计算存在多少令牌。

然后你需要一些方法来检查哪些是令牌。如果它们都是 form A#，这应该很容易。检查第一个（0）。如果它是一个令牌，那么你所有的偶数元素也是令牌。如果不是，则奇数是令牌。

将每个标记的索引存储在一个单独的结构中，可能Map以标记名称作为键，数组索引作为值。

获得排列列表后，您可以将这些短语再次连接到一个新的字符串数组中。例如，复制非令牌片段，然后检查您的映射索引以查看令牌A1的去向。

于 2013-10-23T20:21:51.710 回答