ruby - 随机置换迭代器

Question

需要用新的迭代器扩充 Enumerable 模块，它以随机顺序返回集合元素。关于收集的唯一信息 - 它响应每个。没有关于元素的其他假设。我有一个解决方案 - 将元素包装到 Array 中，然后使用示例方法：

def each_permuted
    tmp = []
    self.each do |w|
        tmp << w
    end
    tmp.sample(tmp.length).each do |w|
        yield w
    end
end

不喜欢它，因为这里我们经过两次收集（甚至三次计算 tmp.sample 随机排列）。单程可以吗？

Answer 1

我怀疑是否有可能与signle go through有关。看看这个页面：http ://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_.22inside-out.22_algorithm

我在文章中实现了名为“由内而外的算法”的算法（它经过两次收集）：

def each_permuted
  generator = Random.new
  tmp = []
  self.each do |w|
    r = generator.rand(tmp.size + 1)
    if r == tmp.size
      tmp << w
    else
      tmp << tmp[r]
      tmp[r] = w
    end
  end

  tmp.each do |w|
    yield w
  end
end

测试：

1.9.3p327 :064 > [1,2,3,4,5,6].each_permuted { |x| p x }
1
5
2
6
3
4
 => [1, 5, 2, 6, 3, 4]
1.9.3p327 :065 > [1,2,3,4,5,6].each_permuted { |x| p x }
4
3
2
5
6
1
 => [4, 3, 2, 5, 6, 1]
1.9.3p327 :066 > [1,2,3,4,5,6].each_permuted { |x| p x }
4
5
2
1
3
6
 => [4, 5, 2, 1, 3, 6]

Answer 2

def each_permuted ≺ shuffle.each(&pr) end