1

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

我现在拥有的是这样的：

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

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

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

我能做些什么？

更新：

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

4

4 回答 4

4

您的调用map(&:join)是在内存中创建数组，因为map实际上将 Enumerator 变成了数组。根据您想要执行的操作，您可以避免使用以下内容创建数组：

def each_permutation(string)
  string.split(//).permutation do |permutaion|
    yield permutation.join
  end
end

然后像这样使用这个方法：

each_permutation(my_string) do |s|
  lookup_string(s) #or whatever you need to do for each string here
end

这不会检查重复项（不调用uniq），但会避免创建数组。对于大字符串，这仍然可能需要很长时间。

但是，我怀疑在您的情况下，有更好的方法可以解决您的问题。

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

看起来您正在寻找现有单词列表中可能的字符串字谜。如果你取任意两个字谜并对其中的字符进行排序，得到的两个字符串将是相同的。您是否可以更改您的数据结构，以便您拥有一个哈希，其中键是已排序的字符串，值是作为该字符串的字谜的单词列表。然后，无需根据列表检查新字符串的所有排列，您只需对字符串中的字符进行排序，并将其用作键来查找作为该字符串排列的所有字符串的列表。

于 2013-02-03T05:21:00.850 回答
4

也许您不需要生成集合的所有元素，而只需要生成随机或受约束的子集。我编写了一个算法来在 O(n) 时间内生成第 m个排列。

首先将键转换为阶乘数字系统中自身的列表表示。然后迭代地在新列表和旧列表指定的每个索引处提取项目。

module Factorial
  def factorial num; (2..num).inject(:*) || 1; end

  def factorial_floor num
    tmp_1 = 0
    1.upto(1.0/0.0) do |counter|
      break [tmp_1, counter - 1] if (tmp_2 = factorial counter) > num
      tmp_1 = tmp_2     #####
    end                # # 
  end                 #   #
end                        # returns [factorial, integer that generates it]
                            # for the factorial closest to without going over num

class Array; include Factorial
  def generate_swap_list key   
    swap_list = []              
    key -= (swap_list << (factorial_floor key)).last[0] while key > 0
    swap_list
  end

  def reduce_swap_list swap_list
    swap_list = swap_list.map   { |x|       x[1]                    }
    ((length - 1).downto 0).map { |element| swap_list.count element }
  end

  def keyed_permute key
    apply_swaps reduce_swap_list generate_swap_list key
  end

  def apply_swaps swap_list
    swap_list.map { |index| delete_at index }
  end
end

现在，如果你想随机采样一些排列，ruby 自带Array.shuffle!，但这会让你复制和保存排列或遍历permutohedral 空间。或者，也许有一种方法可以根据您的目的限制排列空间。

constrained_generator_thing do |val|
    Array.new(sample_size) {array_to_permute.keyed_permute val}
end
于 2013-12-08T19:00:45.397 回答
4

只是重申一下Sawa所说的。你了解范围吗？n任何元素的排列数是n!。这是关于你能得到的最激进的数学级数运算。n1-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 数据中心，否则您将在这里非常不走运:)

于 2013-02-02T23:34:41.583 回答
0

也许我错过了明显的，但为什么不这样做

['a','a','b'].permutation.to_a.uniq!
于 2013-02-02T23:19:39.677 回答