生成给定字符串的所有可能的字母组合（最多 2 个字母）的算法

Question

生成给定字符串的所有可能字母组合（最多 2 个字母）的算法

尝试在 AS3 中创建 Anagram 求解器，例如此处找到的这个：

http://homepage.ntlworld.com/adam.bozon/anagramsolver.htm

我在为各种长度生成所有可能的字母组合时遇到问题字符串。如果我只是生成固定长度的排列，这对我来说不会是一个问题......但我希望减少字符串的长度并从原始字母集中获取所有可能的排列最大长度小于原始字符串的字符串。例如，假设我想要一个长度为 2 的字符串，但我有一个 3 个字母的字符串“abc”，则输出将为：ab ac ba bc ca cb。

理想情况下，该算法会生成一个完整的可能组合列表，从原始字符串长度开始，一直到最小字符串长度 2。我有一种感觉，可能有一个小型递归算法可以做到这一点，但我无法理解它。我在 AS3 中工作。

谢谢！

Answer 1

为了编写您链接的类型的字谜解算器，您所请求的算法不是必需的。它也非常昂贵。

例如，让我们看一下像 MONKEY 这样的 6 个字母的单词。该单词的所有 6 个字母都不同，因此您将创建：

• 6*5*4*3*2*1 不同的 6 字母单词
• 6*5*4*3*2 不同的 5 字母单词
• 6*5*4* 3 个不同的 4 字母单词
• 6*5*4 不同的 3 字母单词
• 6*5 不同的 2 字母单词
• 总共 1950 个单词

现在，大概您不想吐出所有 1950 个单词（例如“OEYKMN”）作为字谜（确实如此，但其中大多数也是胡言乱语）。我猜你有一本合法英语单词的字典，你只想检查这些单词是否是查询单词的字谜词，可以选择不使用所有字母。

如果真是这样，那么问题就简单了。

要确定 2 个单词是否是彼此的字谜词，您需要做的就是计算每个字母的使用次数，然后比较这些数字！

让我们将自己限制为仅 26 个字母 AZ，不区分大小写。您需要做的是编写一个函数 countLetters，它接受一个单词并返回一个包含 26 个数字的数组。数组中的第一个数字对应于单词中字母 A 的计数，第二个数字对应于 B 的计数，依此类推。

然后，两个单词 W1 和 W2 是精确的字谜，如果对于每个 i 都有 countLetters(W1)[i] == countLetters(W2)[i] ！也就是说，每个单词使用每个字母的次数完全相同！

对于我所说的子字谜（MONEY 是 MONKEY 的子字谜），W1 是 的子字谜>W2 如果对于每个 i 都有 countLetters(W1)[i] <= countLetters(W2)[i]！也就是说，子字谜可以使用较少的某些字母，但不能使用更多！

（注意：MONKEY 也是 MONKEY 的子字谜）。

---

这应该为您提供一个足够快的算法，其中给定查询字符串，您所需要做的就是通读字典一次，将每个单词的字母计数数组与查询单词的字母计数数组进行比较。您可以做一些小的优化，但这应该足够好了。

或者，如果您想要最佳性能，您可以预处理字典（预先知道）并创建子字谜关系的有向非循环图。

下面是这样一个图的一部分用于说明：

 D=1,G=1,O=1  ----------> D=1,O=1
  {dog,god}   \            {do,od}
               \
                \-------> G=1,O=1
                           {go}

基本上每个节点都是具有相同字母计数数组的所有单词的存储桶（即它们是精确的字谜词）。如果 N2 的数组是 <= （如上面定义的），则有一个从 N1 到 N2 的节点N1 的数组（您可以执行传递归约以存储最少量的边）。

然后，要列出一个单词的所有子字谜，您所要做的就是找到与其字母计数数组对应的节点，并递归地探索从该节点可到达的所有节点。他们所有的桶都将包含子字谜。

Answer 2

下面的js代码将找到n个字母的单词中所有可能的“单词”。当然，这并不意味着它们是真实的单词，但确实为您提供了所有组合。在我的机器上，一个 7 个字母的单词大约需要 0.4 秒，一个 9 个字母的单词需要 15 秒（如果没有重复的字母，多达近一百万种可能性）。然而，这些时间包括查字典并查找哪些是真实的单词。

var getWordsNew=function(masterword){
var result={}
 var a,i,l;
function nextLetter(a,l,key,used){
     var i;
    var j;
    if(key.length==l){
        return;
    }
    for(i=0;i<l;i++){
        if(used.indexOf(""+i)<0){
            result[key+a[i]]="";
            nextLetter(a,l,key+a[i],used+i);
        }
    }
 }
a=masterword.split("");
  l=a.length;
for (i = 0; i < a.length; i++) {
    result[a[i]] = "";
    nextLetter(a, l, a[i], "" + i)
}
return result;
}

完整代码位于

用于在单词中查找单词的代码

Answer 3

你想要某种安排。如果您熟悉排列算法，那么您就会知道您需要检查以查看何时生成了足够的数字。只需更改该限制即可：

我不知道 AS3，但这里有一个伪代码：

st = an array
Arrangements(LettersInYourWord, MinimumLettersInArrangement, k = 1)
  if ( k > MinimumLettersInArrangements )
  {
    print st;
  }

  if ( k > LettersInYourWord )
    return;      

  for ( each position i in your word that hasn't been used before )
    st[k] = YourWord[i];
    Arrangements(<same>, <same>, k + 1);

for "abc" and Arrangements(3, 2, 1);这将打印：

ab
abc
ac
acb
...

如果您想要先有三个，然后有两个，请考虑以下内容：

st = an array
Arrangements(LettersInYourWord, DesiredLettersInArrangement, k = 1)
  if ( k > DesiredLettersInArrangements )
  {
    print st;
    return
  }

  for ( each position i in your word that hasn't been used before )
    st[k] = YourWord[i];
    Arrangements(<same>, <same>, k + 1);

然后对于“abc”，调用 Arrangements(3, 3, 1); ，然后 Arrangements( 3, 2, 1);

Answer 4

您可以通过查找完整字母图中的所有路径来生成字母表中的所有单词。您可以通过从每个字母进行深度优先搜索并返回每个点的当前路径来找到该图中的所有路径。

Answer 5

有简单的 O(N)，其中 n 是词汇量的大小。
只需对词汇表中每个单词中的字母进行排序或更好，创建它们的二进制掩码，然后比较您拥有的字母。