Re: Is this a fair shuffle?

I have only been trying to learn perl for about 2 months but couldn't you just iterate through your array and generate a random number between 0-19 then give your current array address the value from the random array address. so something like

my $random = int( rand(20));

foreach $array (@array){
    $store = $array;
    $array = $array[$random];
    $array[$random] = $store;
    $random = int( rand(20));
}
[download]

The code is probably wrong because I am a noob with perl and programing in general but that is my idea, and I thought this post was extremely interesting at least considering my level of knowledge about perl.

Comment on Re: Is this a fair shuffle? Download Code

Replies are listed 'Best First'.
Re^2: Is this a fair shuffle? by Roy Johnson (Monsignor) on Apr 01, 2005 at 20:15 UTC
I appreciate your trying to be helpful, but I wasn't actually looking for a good way to do a shuffle (that problem has been well solved by List::Util 'shuffle'). I was wondering whether a novel (or what I thought was a novel) way of shuffling was fundamentally flawed. (It was.) For more on how to do shuffles right and wrong, see A bad shuffle. And welcome to the wonderful world of Perl. Caution: Contents may have been coded under pressure.	[reply]
Re^2: Is this a fair shuffle? by Anonymous Monk on Apr 01, 2005 at 19:42 UTC
Along the lines you mentioned, this works: `my @shuffled = map { $_->[0] } sort { $a->[1] <=> $b->[1] } map { [ $_, rand() ] } @unshuffled;` [download] But compared to other approaches it is slow and memory-expensive. This topic came up at a recent kw.pm meeting, and I played around and did some rudimentary benchmarks: http://kw.pm.org/wiki/index.cgi?ListShuffle 2005-04-02 Janitored by Arunbear - replaced pre tags with code tags, to allow code extraction	[reply] [d/l]
Re^3: Is this a fair shuffle? by Thargor (Scribe) on Apr 01, 2005 at 19:55 UTC
Hey even though I didn't start this question it is really interesting to me. Could you explain, point to somewhere I can read about it, or otherwise instruct me as to why my solution is slow. I see lots of posts with map and such in them and I have no clue about its function so I assume it will come up later in my reading of the llama book. And thankyou to any who take the time to give me some information on this subject.	[reply]
Re^4: Is this a fair shuffle? by fishbot_v2 (Chaplain) on Apr 01, 2005 at 21:59 UTC
Well, I pointed to the link with the discussion: http://kw.pm.org/wiki/index.cgi?ListShuffle ...but here is a quick summary. Your algorithm (and my mostly equivalent one) are memory expensive because they have to allocate for a random number for each element in the list. If you are sorting numbers, this amounts to a doubling of the memory footprint. It is slow because it is two pass, the first O(N), the second (the sort) O(NlogN). That's not terribly slow, but list shuffling can be accomplished with O(N) running time. So, a pure perl swap-shuffle is about 4 times faster, and the List::Util version is about 70 times faster, depending, of course on list-size.	[reply]
Re^3: Is this a fair shuffle? by Anonymous Monk on Apr 01, 2005 at 19:45 UTC
Sorry, I don't post here often and didn't preview as well as I should have. That should obviously have been: `my @shuffled = map { $_->[0] } sort { $a->[1] <=> $b->[1] } map { [ $_, rand() ] } @unshuffled;` [download]	[reply] [d/l]