8

生成给定字符串的所有可能字母组合的算法，低至 2 个字母

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

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

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

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

谢谢！

4

5 回答 5

8

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

让我们看一个 6 个字母的单词MONKEY，例如，。该单词的所有 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，依此类推。

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

对于我所说的子字谜（MONEY是 的子字谜MONKEY），W1是W2if countLetters(W1)[i] <= countLetters(W2)[i]for each 的子字谜i！也就是说，子字谜可能会使用更少的某些字母，但不会更多！

（注：MONKEY也是 的子变位词MONKEY）。

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

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

以下是此类图表的一部分用于说明：

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

基本上，每个节点都是具有相同字母计数数组的所有单词的存储桶（即它们是精确的字谜）。然后有一个节点 from N1to N2ifN2的数组是<=（如上定义）N1的数组（您可以执行传递缩减以存储最少数量的边）。

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

于 2010-03-13T21:20:04.863 回答
3

下面的 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;
}

完整代码在

在单词中查找单词的代码

于 2012-12-05T06:22:10.077 回答
0

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

我不知道 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);

对于“abc”和安排（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);

于 2010-03-13T18:22:28.443 回答
0

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

于 2010-03-13T20:41:47.250 回答
0

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

于 2010-03-14T12:16:50.610 回答