[kw-pm] Doctor Perl

[Eric - fishbot]

List::Util shuffle -is- Fisher-Yates:
(I've also seen this called a 'Knuth Shuffle')

   sub shuffle (@) {
     my @a=\(@_);
     my $n;
     my $i=@_;
     map {
       $n = rand($i--);
       (${$a[$n]}, $a[$n] = $a[$i])[0];
     } @_;
   }

Except List::Util provides a XS implementation as well.  And without the
devious use of map seen above.  As far as I can tell, folding the swap
into a single statement is pure masochism.  I'm tempted to benchmark, but
that's just masochism being contagious.

Another nice shuffle is this:

   @list = map { $_->[0] }
           sort { $a->[1] <=> $b->[1] }
           map { [ $_, rand( @list ** 2 ) ] }
           @list;

Which is more expensive, but I benchmarked it at 0.25 seconds for our
10816 list, so the expense likely isn't noticeable.  (...though it is 8 times
slower than the XS shuffle.  If you were shuffling anything bigger than a
scalar, though, I think that this would widen quickly.)

I don't know much about XLST, I am afraid, though I notice that eXSLT
implements a rand() somehow.  You could look into that.  I doubt that an
all XLST solution would be very clean, but I get the impression that you
are looking to do a proof-of-concept, and thus practicality is irrelevant.

fishbot

---- original message : 2005-03-01 2:32am : lloyd carr ----

Dear Doctor Perl,
I could use this-

use List::Util shuffle;
my @tiles = 0..10816;
shuffle( @tiles );

or this-

my @array = 0..10816;

# fisher_yates_shuffle( \@array ) :
# generate a random permutation of @array in place
sub fisher_yates_shuffle {
	my $array = shift;
	my $i;
	for ($i = @$array; --$i; ) {
		my $j = int rand ($i+1);
		next if $i == $j;
		@$array[$i,$j] = @$array[$j,$i];
	}
}

fisher_yates_shuffle( \@array );    # permutes @array in place

but what I'd really like to know is there a way to do the Fisher-Yates
shuffle in XSLT/eXSLT?

-Lloyd

dcarr at sdf.lonestar.org
SDF Public Access UNIX System - http://sdf.lonestar.org
_______________________________________________
kw-pm mailing list
kw-pm at pm.org
http://mail.pm.org/mailman/listinfo/kw-pm