ruby - 如何使用更少的内存生成数组排列？

Question

所以我需要得到一个字符串所有可能的排列。

我现在拥有的是:

def uniq_permutations string
  string.split(//).permutation.map(&:join).uniq
end

好的，现在我的问题是什么:这种方法适用于小字符串，但我希望能够将它用于大小为 15 甚至 20 的字符串。使用这种方法会占用大量内存(>1gb) 我的问题是我可以改变什么来不使用那么多内存？

有没有更好的方法来生成排列？我是否应该将它们保存在文件系统中并在需要时检索它们(我希望不是因为这可能会使我的方法变慢)？

我能做什么？

更新:

我实际上不需要将结果保存在任何地方，我只需要在表中查找每个结果以查看它是否存在。

Answer 1

只是重申 Sawa 所说的话。你了解范围吗？任何 n 元素的排列数为 n!。这是关于您可以获得的最激进的数学级数运算。 n 在 1-20 之间的结果是:

[1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 
 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000,
 6402373705728000, 121645100408832000, 2432902008176640000]

最后一个数字大约是 2 quintillion，即 20 亿。

也就是 2265820000 GB。

您可以全天将结果保存到磁盘上 - 除非您拥有世界上所有的 Google 数据中心，否则您将在这里运气不佳:)