On Fri, Apr 12, 2002 at 03:09:27PM +0300, Ilmari Karonen wrote:
> On Tue, 9 Apr 2002 [EMAIL PROTECTED] wrote:
> > On Tue, Apr 09, 2002 at 01:49:01PM +0300, Ilmari Karonen wrote:
> > > On Fri, 5 Apr 2002 [EMAIL PROTECTED] wrote:
> > > >
> > > > sub shuffle {
> > > > for (my $i = @_; $i;) {
> > > > my $j = rand $i --;
> > > > @_ [$i => $j] = @_ [$j => $i]
> > > > }
> > > > @_;
> > > > }
> > >
> > > It doesn't, unfortunately, allow for the idiom one expects from a
> > > copy-and-shuffle function, namely
> > >
> > > my @shuffled = shuffle @original;
> >
> > It allows for:
> >
> > my @shuffled = shuffle 1 .. 10;
>
> Not very consistently, though:
>
> my @shuffled = shuffle 'A',2,3,4,5,6,7,8,9,10,'J','Q','K';
> Modification of a read-only value attempted at - line 4.
Eew. That looks like a bug in perl somewhere.
shuffle 1 .. 10; # Fine.
shuffle 1, 2, 3, 4, 5, 6, 7, 8, 9, 10; # Not ok.
> > I do think it needs a reference to Knuth [1]. Or to the original publication
> > of Fisher and Yates [2].
> >
> > [1] D. E. Knuth: I<The Art of Computer Programming>, Volume 2,
> > Third edition. Section 3.4.2, Algorithm P, pp 145. Reading:
> > Addison-Wesley, 1997. ISBN: 0-201-89684-2.
> >
> > [2] R. A. Fisher and F. Yates: I<Statistical Tables>. London, 1938.
> > Example 12.
>
> So, how _does_ one properly mark that up in POD? There are no real
> footnotes, and embedding the entire reference in the text would mess up
> the already strained flow of the paragraph. Hmm... :-(
>From Algorithms::Numerical::Shuffle.pm:
=head1 LITERATURE
The algorithm used is discussed by Knuth [3]. It was first published
by Fisher and Yates [2], and later by Durstenfeld [1].
=head1 CAVEAT
Salfi [4] points to a big caveat. If the outcome of a random generator
is solely based on the value of the previous outcome, like a linear
congruential method, then the outcome of a shuffle depends on exactly
three things: the shuffling algorithm, the input and the seed of the
random generator. Hence, for a given list and a given algorithm, the
outcome of the shuffle is purely based on the seed. Many modern computers
have 32 bit random numbers, hence a 32 bit seed. Hence, there are at
most 2^32 possible shuffles of a list, foreach of the possible algorithms.
But for a list of n elements, there are n! possible permutations.
Which means that a shuffle of a list of 13 elements will not generate
certain permutations, as 13! > 2^32.
=head1 REFERENCES
=over
=item [1]
R. Durstenfeld: I<CACM>, B<7>, 1964. pp 420.
=item [2]
R. A. Fisher and F. Yates: I<Statistical Tables>. London, 1938.
Example 12.
=item [3]
D. E. Knuth: I<The Art of Computer Programming>, Volume 2, Third edition.
Section 3.4.2, Algorithm P, pp 145. Reading: Addison-Wesley, 1997.
ISBN: 0-201-89684-2.
=item [4]
R. Salfi: I<COMPSTAT 1974>. Vienna: 1974, pp 28 - 35.
=back
Abigail
