RE (tilly) 4: Fisher-Yates Shuffle

Pride goeth before the fall.

:-(

I may be good at math, but I have not been doing math for a number of years, and after a while you start to get stupid. Like I was above.

Everything that I said is true, except that the average number of collisions is actually 1/n + 1/n + ... + 1/n, and not 1+1/2+1/3+...+1/n.

Rather important detail that. :-(

So read the math, it is kind of fun except for that rather basic mistake. Then go looking up the hat-check problem.

(/me feels like an idiot...)

Which makes that branch make even less sense incidentally.

Comment on RE (tilly) 4: Fisher-Yates Shuffle

Replies are listed 'Best First'.
Silly Tilly :-( by tilly (Archbishop) on Aug 30, 2000 at 14:45 UTC
Don't post late either. Posting math before bed is just as bad as posting code. The above "correction" applies to how many elements wind up where they started. The algorithm commentary applies to how many times you make a useless swap. Those are different things. sigh	[reply]
RE: Silly Tilly :-) by Adam (Vicar) on Aug 30, 2000 at 20:45 UTC
Don't worry about it, we all make mistakes. Besides, you really did have it right the first time, and your correction is the mistake. It just goes to show that you are usually right the first time.	[reply]
RE (tilly) 2: Silly Tilly :-) by tilly (Archbishop) on Aug 30, 2000 at 21:09 UTC
...you are usually right the first time. I wish... :-)	[reply]