Empty Elements

dopey has asked for the wisdom of the Perl Monks concerning the following question:

I wanted to write the card game mentioned here. Being too lazy to install the Arthmetic:: Numerical::Shuffle module I decided to make to improvise. My deck would be(until I got Shuffle.pm) cards numbered 1 through 100. In order to "shuffle" the deck I used this:

foreach(1..100){
    do{$i = rand(99)}while exists($seen{$i});
    $seen{$i} = 1;
    $DECK[$i] = $1;
}
[download]

But now I'm getting a bunch of empty elements in $DECK. Why?

Comment on Empty Elements Download Code

Replies are listed 'Best First'.
Fisher-Yates Shuffle (was Re: Empty Element) by Arguile (Hermit) on Jun 09, 2003 at 05:07 UTC
The algorithm from Arithmetic::Numerical::Shuffle is actually the Fischer-Yates shuffle (at least it was last time I checked). For easy reference perlfaq4 answers this question with that same algorithm. Just copy and paste if you want. The alternate version below was authored by Abigail. It does an inplace shuffle and can take a list as an argument (instead of just an array reference). `sub shuffle { for (my $i = @_; $i;) { my $j = rand $i --; @_ [$i => $j] = @_ [$j => $i] } @_; }` [download] As to your code, two main problems. First of all `int(rand($x))` is what you want. Otherwise you get fractional numbers and so appear unique in your `%seen` hash, but don’t to array subscripts which use them as ints. Next is `$DECK[$i] = $1;`, what I think you meant is `$DECK[$_] = $i`. The variable `$1` is for regex matching... did you perhaps mean `$_`? Either way I’d suggest using the Fisher-Yates shuffle instead, once you’ve ponder it’s workings. It’s a much more efficient method.	[reply] [d/l] [select]
Re: Empty Elements by chromatic (Archbishop) on Jun 09, 2003 at 04:37 UTC
Where is the regular expression you expect to set `$1`? Did you mean `$i` or `$_` instead? If you do mean `$1`, do you know the regex matched? perlfaq4 has a nice implementation of the Fisher-Yates algorithm that will work for you.	[reply] [d/l] [select]
Re: Empty Elements by MarkM (Curate) on Jun 09, 2003 at 04:47 UTC
I believe you intended your second last line to read: `$DECK[$_-1] = $i;` Note, however, that your algorithm wastes valuable entropy, and is inefficient. Wasted entropy can reduce the effective period of a rand() function. The inner loop could also, in theory, loop indefinately (although for the expected scenario, it would loop 100 times or less).	[reply] [d/l]
Re: Empty Elements by adrianh (Chancellor) on Jun 09, 2003 at 08:21 UTC
Being too lazy to install the Arthmetic:: Numerical::Shuffle module There's also List::Util's `shuffle` - core if you're using Perl 5.8	[reply] [d/l]
Re: Empty Elements by dopey (Sexton) on Jun 09, 2003 at 05:45 UTC
I meant `$DECK[$i] = $_`	[reply] [d/l]