actionscript-3 - 生成给定字符串的所有可能字母组合的算法，最多 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

为了编写您链接的那种变位词求解器，您所请求的算法不是必需的。它也非常昂贵。

让我们看一个由 6 个字母组成的单词，例如 MONKEY ， 例如。单词的所有 6 个字母都不相同，因此您可以创建:

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

现在，大概您不想将所有 1950 个单词(例如“OEYKMN”)吐出为变位词(确实如此，但其中大部分也是乱码)。我猜你有一本合法英语单词的字典，你只想检查这些单词是否是查询单词的变位词，可以选择不使用所有字母。

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

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

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

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

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

(注意:MONKEY 也是 MONKEY 的子字谜)。

---

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

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

以下是此类图表的一部分以供说明:

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

基本上每个节点都是具有相同字母计数数组(即它们是精确的字谜)的所有单词的桶。然后有一个来自 N1 的节点至 N2如果N2的数组是 <= (定义如上)N1的数组(您可以执行传递归约以存储最少量的边)。

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