Ruby中的Map方法给出了错误

Question

"aaabbb".chars.to_a.permutation.map(&:join).uniq 

正确工作并提供所需的输出,即使用给定字符串可以形成的所有单词,但如果字符串是"cdcdcdcdeeeef"或"cdefghmnopqrstuvw"而不是"aaabbb",则相同的代码将失败.我刚试过这三个测试用例,其中三个失败.

"cdefghmnopqrstuvw".chars.to_a.permutation.map(&:join).uniq 

上面的代码行不会返回任何结果.它似乎进入了无限循环.

出了什么问题？

Answer 1

有n!n个元素的排列.所以如果以"cdcdcdcdeeeef"为例,那就有13个!= 6227020800可能的排列,因此计算结果需要很长时间.你的另一个例子有17个字符,导致17个字符!= 3.56*10 ^ 14个排列,这将是"永远".

编辑:更好的解决方案是迭代"aaabbb".chars.to_a.permutation并自己创建结果数组.要获得uniq-functionality,您可以检查当前检查的元素是否已存在于结果中.但是,这只需要更少的内存,但需要的时间与您的方法一样长.我担心,没有直截了当地克服这个问题.在最坏的情况下,根本没有办法加快计算速度.如果没有重复的字符,那么结果必须包含n!元素.但是,如果有重复的字符,可能有一种方法,但我不知道.