From: Matthew Smillie Date: 2006-06-20T00:21:27+09:00 Subject: Re: Is it more convenient to have a random_each in ruby stdlib? On Jun 19, 2006, at 14:46, Alex Young wrote: > Matthew Smillie wrote: >> On the other hand, people who REALLY care about unbiased shuffles >> will already know how to do them. > The problem with this argument is that people might not know when > they need them, and their not being unbiased when you've implicitly > made that assumption sounds like the sort of thing that would > generate really subtle problems. Correct me if I'm wrong... No, you're right. The catch, as usual, comes down to something being "good enough in practice". It's a big circular argument: if you don't know that you need a perfect shuffle, then you're unlikely to actually need one (a biased one is often good enough). If you do know you *need* a perfect shuffle, you're likely to code your own rather than relying on library code, since it's simple enough to do so. I don't actually have much preference either way for including any sort of shuffle in Array or Enumerable or wherever, I was just presenting pros/cons I could think of. > You've given a good explanation of the shuffle principle below, and > that's great for when you want to actually reorder things, but what > if you want to walk across the Enumerable without modifying it? > Did I really mean "perfect hash functions" when I wrote > "quasirandom sequences?" "Perfect hash functions" makes more sense to me in this context, anyway - I'm not aware that quasi-random sequences make any once-and- only-once guarantee the same way a perfect hash function does, they just guarantee a uniform distribution within a certain tolerance/ discrepancy. I might be missing something subtle. Or something obvious, for that matter; I wouldn't know, since I'm the one missing it. Anyway, that's the approach I used in Array#shuffle. The shuffled array of indices defines a perfect hash function for the original array: each key/index in the original array is mapped to a distinct integer; they key/index in the shuffled array of indices. Illustration: original array: arr = ['a', 'b', 'c', 'd'] shuffled array of indices: [2, 0, 1, 3] implicit perfect hash function: 0 => 2, 1 => 0, 2 => 1, 3 => 3 application of the function to arr[0..size]: ['c', 'a', 'b', 'd'] You can see in the implementation that providing a block parameter to Array#shuffle does walk across the entire Array without modifying it. Without the block parameter, it returns a new, shuffled Array. matthew smillie.