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

Question

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

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

Answer 1

也许 lazy 是一个选项。在检查特殊条件之前，它不需要像生成所有排列那样多的内存。

类似于：

'my_string'.chars.permutation.lazy.map(&:join).each do |permutation|    
  puts permutation if dictionary.include?(permutation)
end

Answer 2

如果我们查看 Permutation，我们会看到一个没有重复字母的 11 个字母单词的排列数为 39,916,800。但是对于 MISSISSIPPI，它是 11！ /（1！* 4！* 4！* 2！）= 34,650。不管你怎么做，第一个都需要很长时间，但如果你可以减少搜索 space 使用重复字符，它可能会变得更易于管理。标准排列方法不会删除重复项。

搜索 "ruby permutations without repetition" 可能会找到一些算法。

Answer 3

I am currently using this function, and the code works exactly as it should.
self.chars.permutation.map(&:join).uniq.group_by(&:chr)

However, once the string is more than 10 characters, it takes a lot of time to generate all permutations. How could I generate permutations quicker?

你不能。好吧，也许有一些方法可以加快它的速度，但实际上没有任何意义：排列的数量太多了。对于仅 25 个字符，即使我们假设您可以为每个 CPU 周期生成一个排列，即使我们假设您有 5GHz CPU，即使我们假设您的 CPU有 100 个核心，即使我们假设工作可以完美地分布在这些核心之间，它仍然需要接近一 百万年 才能生成。就这么多。

简而言之：即使尝试加速您的算法也毫无意义。您需要完全避免生成排列。

Answer 4

理论

不需要排列:

对字符串中的字母进行排序
对字典中每个单词的字母进行排序
查找相同排序的字母
完成！

实施

class String
  def sorted_letters
    downcase.chars.sort.join
  end
end

class AnagramFinder
  @dict = '/usr/share/dict/american-english'
  class << self
    def get_anagrams(word)
      sorted_dict[word.sorted_letters]
    end

    def all
      sorted_dict.values.select { |anagrams| anagrams.size > 1 }
    end

    def sorted_dict
      @sorted_dict ||= generate_sorted_dict
    end

    private

    def generate_sorted_dict
      File.foreach(@dict).with_object(Hash.new { |h, k| h[k] = [] }) do |word, sorted_dict|
        word.chomp!
        sorted_dict[word.sorted_letters] << word
      end
    end
  end
end

p AnagramFinder.get_anagrams('impressiveness')
#=> ["impressiveness", "permissiveness"]
p AnagramFinder.get_anagrams('castor')
#=> ["Castor", "Castro", "Croats", "actors", "castor", "costar", "scrota"]
p AnagramFinder.all.last(5)
#=> [["wist", "wits"], ["withers", "writhes"], ["woodworm", "wormwood"], ["wriest", "writes"], ["wrist", "writs"]]
p AnagramFinder.all.max_by(&:length)
#=> ["Stael", "Tesla", "least", "slate", "stale", "steal", "tales", "teals"]

这个例子在我较慢的服务器上需要 0.5 秒，其中大部分时间都花在了构建排序字典上。一旦完成，查找几乎是即时的。

"impressiveness" 有 14 个字符，您需要非常很长时间才能生成所有排列 (14!= 87178291200)。

Answer 5

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

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"]}

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

How can I quickly generate all permutations of a string in Ruby?

ruby

math

permutation

理论

实施