Random permutation iterator

Question

Need to augment Enumerable module with new iterator, that returns elements of collection in random order. The only information about collection - it responds to each. No other assumptions about elements. I have a solution - to wrap elements into Array and then use sample method:

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

Don't like it, because here we go through collection twice(even three times counting tmp.sample random permutation). Is it possible with single go through?

Answer 1

I doubt that it is possible to do with signle go through. Take a look at this page: http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_.22inside-out.22_algorithm

I implemented the algorithm named "the inside-out algorithm" in the article (it goes through collection twice):

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

Tests:

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]