#!/usr/bin/perl -w package Algorithm::Numerical::WeightedShuffle; ###################### # # Algorithm::Numerical::WeightedShuffle; # v0.01 # Michael K. Neylon # mneylon-pm@masemware.com # May 27, 2001 # # Shuffles a list based on weights, as to have items with # heavier weights to have a better chance of being located # earlier in the shuffled list # # Loosely based and borrowed from Abigail's # Algorithm::Numerical::Shuffle # # Suggestions/Comments/Ideas are highly desired and can be # sent to the eamil address above. # # Change History: # # v0.01 - May 27, 2001 # - Initial Release # ###################### use strict; use Exporter; use vars qw /$VERSION @ISA @EXPORT @EXPORT_OK/; @ISA = qw /Exporter/; @EXPORT = qw //; @EXPORT_OK = qw /weightedshuffle weightedshuffleindex/; $VERSION = 0.01; sub weightedshuffle { die "Need two equal length arrays for WeightedShuffle" if !@_ || ref $_[0] ne 'ARRAY' || ref $_[1] ne 'ARRAY' || @{$_[0]} != @{$_[1]}; my ( $list, $weights ) = @_; my @array = map { $list->[ $_ ] } weightedshuffleindex( $weights ); wantarray ? @array : \@array; } sub weightedshuffleindex { return @_ if !@_ || ref $_ [0] eq 'ARRAY' && !@{$_ [0]}; # We need a copy here, since we destroy it my @weights = @_ == 1 && ref $_ [0] eq 'ARRAY' ? @{shift()} : @_; my @indices = ( 0..@weights - 1); my @array = (); my $sum = 0; foreach ( @weights ) { $sum += ( $_ > 0 ? $_ : 0 ) }; while ( $sum > 0 ) { my $r = rand $sum ; my $total = 0; my $i = -1; while ( $total < $r ) { $total += ( $weights[ $i+1 ] > 0 ? $weights[ $i+1 ] : 0 ); $i++; } push @array, splice( @indices, $i, 1 ); splice( @weights, $i, 1 ); $sum = 0; foreach ( @weights ) { $sum += ( $_ > 0 ? $_ : 0 ) +}; } # anything left over, push to the end push @array, @indices; wantarray ? @array : \@array; } __END__ =head1 NAME Algorithm::Numerical::WeightedShuffle - Shuffle a list using weights. =head1 SYNOPSIS use Algorithm::Numerical::WeightedShuffle qw( weightedshuffle weightedshuffleindex ); @array = ( 1..10 ); @weights = map { $_*$_ } @array; @shuffled = weightedshuffle( \@array, \@weights ); %hash = ( one=>1, two=>2, three=>3, four=>4, five=>5 ); my @keys = keys %hash; @shuffled_keys = map { $keys[$_] } weightedshuffleindex( map { $hash{ $_ } } @keys ); =head1 DESCRIPTION C<weightedshuffle> takes two array references; the first is the list to be shuffled, while the second are the weights for the items in this list. The list is then shuffled such that items with higher weights w +ill have a better chance of appearing earlier in the returned list. Weights should be non-zero positive numbers, but need not sum to 1; negative or zero weights will be ignored and items associated with these will simply be appended to the end of the list. The subroutine returns the list in list context, and a reference to the list in scalar context. C<weightedshuffleindex> takes a single array or array reference, being the list of weights. It then returns an array of indices based on this list, such that indices of larger weights will have a better chance of being earlier in the list. The same requirements for the weights from C<weightedshuffle> apply here as well. The indices array returned by this function can be used further by a map statement, to shuffle the keys of a hash, for example. The subroutine returns the list in list context, and a reference to the list in scalar context. =head1 HISTORY Revision 0.01 2001/05/27 Michael K. Neylon Initial revision =head1 AUTHOR This package was written by Michael K. Neylon =head1 COPYRIGHT Copyright 2001 by Michael K. Neylon =head1 LICENSE Permission is hereby granted, free of charge, to any person obtaining +a copy of this software and associated documentation files (the "Softwar +e"), to deal in the Software without restriction, including without limitat +ion the rights to use, copy, modify, merge, publish, distribute, sublicens +e, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be include +d in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRES +S OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILIT +Y, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHAL +L THE AUTHOR BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. =cut 1;
In reply to Algorithm::Numerical::WeightedShuffle by Masem
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |