Itérateur de permutation aléatoire

Question

Besoin de compléter le module Enumerable avec un nouvel itérateur, qui renvoie les éléments de la collection dans un ordre aléatoire. La seule information sur la collection - il répond à chacun. Aucune autre hypothèse sur les éléments. J'ai une solution - pour envelopper des éléments dans un tableau, puis utiliser la méthode de l'échantillon:

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

ne l'aime pas, parce qu'ici nous traversons collection deux fois (même trois fois le comptage tmp.sample permutation aléatoire). Est-ce possible avec un simple passage?

Answer 1

Je doute que ce soit possible avec signle. Jetez un oeil à cette page: http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_.22inside-out.22_algorithm

I mis en œuvre l'algorithme nommé "l'algorithme inside-out" dans l'article (il passe par la collecte deux fois):

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] 

Answer 2

def each_permuted ≺ shuffle.each(&pr) end