ruby - 如何在 Ruby 中快速生成字符串的所有排列？

Question

我目前正在使用这个函数，代码可以正常工作。
self.chars.permutation.map(&:join).uniq.group_by(&:chr)

但是，一旦字符串超过10个字符，生成所有排列需要花费大量时间。我怎样才能更快地生成排列？

Answer 1

与其计算每个单词的所有排列，更好的方法是首先从字典创建一个散列，其键是按字符排序的字符串，其值是包含字典中所有单词的数组，这些单词是键的变位词。当单词在字典中(除了它本身之外)不包含变位词时，数组为空。

words      = %w| god act bat tar a lion stop |
  #=> ["god", "act", "bat", "tar", "a", "lion", "stop"]
dictionary = %w| cat dog a fowl bat god act lion pig donkey loin post pots
                 spot stop tops| 
  #=> ["cat", "dog", "a", "fowl", "bat", "god", "act", "lion", "pig",
  #    "donkey", "loin", "post", "pots", "spot", "stop", "tops"]

h = dictionary.each_with_object(Hash.new { |h,k| h[k] = [] }) do |w,h|
  h[w.each_char.sort.join] << w
end
  #=> {"act"=>["cat", "act"], "dgo"=>["dog", "god"], "a"=>["a"], "flow"=>["fowl"],
  #    "abt"=>["bat"], "ilno"=>["lion", "loin"], "gip"=>["pig"], "deknoy"=>["donkey"],
  #    "opst"=>["post", "pots", "spot", "stop", "tops"]} 

然后，我们可以通过对单词的字符进行排序并查看它是否是散列中的键来获取 words 中每个单词的所有变位词。

words.each_with_object({}) do |w,g|
  key = w.downcase.chars.sort.join
  values = h.key?(key) ? (h[key]-[w]) : []
  g[w] = values
end
  #=> {"god"=>["dog"], "act"=>["cat"], "bat"=>[], "tar"=>[], "a"=>[],
  #    "lion"=>["loin"], "stop"=>["post", "pots", "spot", "tops"]}