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

为了编写您链接的anagram解算器,您要求的算法不是必需的.它也非常昂贵.

例如,让我们看一个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个不同的双字母单词
• 总共1950个单词

现在,大概你并没有试图吐出所有1950个单词(例如'OEYKMN')作为字谜(他们是,但他们中的大多数也是胡言乱语).我猜你有一个法律英语词典,你只想检查这些词是否是查询词的字谜,可以选择不使用所有字母.

如果是这种情况,那么问题很简单.

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

我们将自己限制为只有26个字母AZ,不区分大小写.你需要做的是编写一个函数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}

基本上每个节点都是一个桶,用于所有具有相同字母数组的单词(即它们是精确的字谜).然后有一个节点从if N1到s的数组是(如上定义的)数组(你可以执行传递减少来存储最少量的边).N2N2<=N1

然后列出单词的所有子字谜,您所要做的就是找到与其字母数组对应的节点,并递归浏览从该节点可到达的所有节点.他们所有的桶都包含子字谜.