1

我正在为我的算法生成一组相当大的数组排列：

argeArray.permutation(permSize) do |perm|
  # Do something with perm
end

现在我正在努力更新应用程序，以便能够在它停止的索引处继续。

环顾四周后，我没有找到permutation具有起始索引（能够跳过0..startIndex）的替代方法。

接下来我找到了能够从排列枚举器中截断第一个元素的drop()方法：

startIndex = 3000000000 # skip first 3 billion combinations
argeArray.permutation(permSize).drop(startIndex) do |perm|
  # Do something with perm
end

但是实验表明，这会创建完整的组合集，这不是很有效，因为它需要大量的内存......即使它只需要跳过前 30 亿个组合......

另一种解决方案是跳过算法，直到startIndex达到：

startIndex = 3000000000 # skip first 3 billion combinations
argeArray.permutation(permSize).with_index() do |perm, index|
  next if index < startIndex # Skip until startIndex is reached
  # Do something with perm
end

缺点是在算法（最终）开始工作之前测试了 30 亿个组合（并且浪费地不断检查是否startIndex达到）

这个问题还有其他（更有效的）解决方案吗？以某种方式能够告诉permutation()跳过初始数量的组合？（假设它总是使用相同的顺序）

4

1 回答 1

1

Ruby 2.0 引入了Enumerator::Lazy. 也许调查一下可能会对您有所帮助。

module Enumerable
  def filter_map(&block)
    map(&block).compact
  end
end

class Enumerator::Lazy
  def filter_map
    Lazy.new(self) do |yielder, *values|
      result = yield *values
      yielder << result if result
    end
  end
end

(1..Float::INFINITY).lazy.filter_map{|i| i*i if i.even?}.first(5)
    # => [4, 16, 36, 64, 100]

您可能可以创建您的排列作为一个实例Enumerator::Lazy并使用它drop来跳到某个位置。

于 2013-06-04T08:25:47.630 回答