1

我正在尝试编写一个小例程，负责排列字符串的所有可能缩写。这个字符串是一个全名，用空格分隔。像这样：

James Mitchell Rhodes

我想输出：

J. Mitchell Rhodes
James M. Rhodes
J. M. Rhodes

等等......但是，我还必须考虑“停用词”：

James the Third Rhodes

我想输出：

J. the Third R.
James The Third R.

有一个已知的算法吗？很长一段时间以来，我一直在尝试解决这个问题。

更新：将每个单词放在数组中很容易。只需explode(' ', $string) 然后array_map，排除停用词考虑in_array($w​​ord, $stopWordsMap)。这不是问题，也不是问题的重点。问题是如何发现可能的原始词（O）和缩写词（A）的组合：

O A A
O A O
O A A
A A A
O O O
4

2 回答 2

2

第一直觉是用 for 循环迭代二进制排列，即去掉停用词（如果你愿意，记住它们的位置），2 ^ numOfRemainingElements，去掉AND每个词的状态（意思是缩写或不缩写）：

$names = array('James', 'Earl', 'Jones');
$nameCount = count($names);
$permCount = pow(2, $nameCount);

for ($p = 1; $p < $permCount; $p++) {
    for ($n = 0; $n < $nameCount; $n++) {
        echo $p & pow(2, $n) ? $names[$n][0] . '.' : $names[$n];
        echo ' ';
    }
    echo "\n";
}

/* output:

J. Earl Jones 
James E. Jones 
J. E. Jones 
James Earl J. 
J. Earl J. 
James E. J. 
J. E. J. 

*/

你可以进一步调整它，但你可以看到我要去哪里。

于 2013-09-17T21:41:07.807 回答
1

我不会写完整的代码，因为你说置换不是问题。这是关于确定在所有场景中置换哪些单词。

我不得不考虑二进制系统，如果你想拥有所有可能的输入到一个有 n 个输入的函数，你需要 2^n 个输入场景。

所以对你来说，你有 2 个输入

0 0
0 1
1 0
1 1

好吧？我们可以将其作为 php 中的数组使用

$map = array();
$inputs = 2;
for($i=0;$i<=2^$inputs;$i++){
    $bin = decbin($i);  // returns string
    $array = preg_split('//', $bin, -1, PREG_SPLIT_NO_EMPTY); // but i want a array
    $map[] = $array;
}

现在，如果您要置换的字符串包含三个单词，请将它们视为三个输入，然后所有 $map 行都会告诉您每次置换哪个单词以获取所有可能的字符串，如果该行中的第一项为 0，不要排列第一个单词，如果是 1 则排列第一个单词，依此类推..

这是您的示例的所有行和结果字符串

0 0 0  James Mitchell Rhodes
0 0 1  James Mitchell R,
0 1 0  James M. Rhodes
0 1 1  James M. R.
1 0 0  J. Mitchell Rhodes
1 0 1  J. Mitchell R.
1 1 0  J. M. Rhodes
1 1 1  J. M. R
于 2013-09-17T21:40:26.540 回答