隨機置換迭代器

需要用新的迭代器來增加Enumerable模塊，該迭代器以隨機順序返回集合的元素。關於收集的唯一信息 - 它對每個信息作出響應。沒有其他關於元素的假設。我有一個解決方案 - 包裝元素融入到數組，然後用樣品的方法：隨機置換迭代器

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

不喜歡它，因爲在這裏我們通過收集兩次（甚至三次tmp.sample隨機排列計數）。單通過可能嗎？

來源

2013-04-02 yarum

如果集合只響應'each'，那麼您必須至少完成一次以完成一個隨機樣本（因爲否則您甚至不知道概率的長度選擇樣品）。 AFAIK沒有辦法。如果採集項目可以通過任何方式進行尋址，那麼您可以根據地址進行採樣。我認爲你的代碼接近最佳。你可以使用'.shuffle'而不是'.sample（tmp.length）' - 雖然我不知道Ruby的內部結構，但是這有可能讓你稍微快一點。 –

enumerable.to_a.shuffle有什麼問題？ – tokland

我懷疑是否有可能做signle通過。看看這個頁面：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]

來源

2013-04-02 11:22:10 DNNX

def each_permuted &pr; shuffle.each(&pr) end

來源

2013-04-02 11:41:20 sawa

編號_關於收集的唯一信息 - 它對each_做出響應。作者沒有說它對「洗牌」或任何其他方法做出了迴應。 – DNNX

我認爲'def each_permuted ≺ to_a.shuffle.each（＆pr）end'雖然是好的，因爲我們增加了'Enumerable'，並且在調用'each'的基礎上增加了'to_a'。 –

隨機置換迭代器

回答

相關問題