[LON-CAPA-users] random_permutation, choosing the $seed
Peter Dencker
dencker at math.uni-luebeck.de
Sun Aug 31 11:52:03 EDT 2014
Hi.
The problem given below compares two procedures to permute lists: sub
'shuffle' is a Fisher-Yates-shuffle procedure and sub 'permute' directly
uses the script function 'random_permutation'. The latter shows a
remarkable imbalance. This seems to be a bias as it remains stable if
choosing other randomization.
All my tries to choose the $seed give a similar behavior.
What is the right method?
- Peter
<problem>
<script type="loncapa/perl">
our $N = 10000;
sub shuffle {
my @values = @_;
return
if !@values;
for my $i ( 0 .. $#values - 1 ) {
my $j = random( $i, $#values, 1 );
@values[ $i, $j ] = @values[ $j, $i ];
}
return @values;
}
sub permute {
my @values = @_;
return
if !@values;
my $seed = random( 1, 1E10, 1 );
return random_permutation( $seed, @values );
}
our $tables;
for ( 'B' .. 'E' ) {
my @items = 'A' .. $_;
$tables .= '$N random permutations of '
. ( join q{}, @items ) . ' counted: <br />';
my %number;
for ( 1 .. $N ) {
$number{'permute'}{ join q{}, permute @items }++;
$number{'shuffle'}{ join q{}, shuffle @items }++;
}
$tables
.= '<table border=1><tr><td>permutation</td>'
. '<td>shuffle</td>'
. '<td>permute</td></tr>'
. '<tr><td align="center">'
. join '</td></tr><tr><td align="center">', map {
join '</td><td align="right">',
$_, $number{'shuffle'}{$_},
$number{'permute'}{$_};
} sort { $a cmp $b }
keys %{ $number{'shuffle'} };
$tables .= '</td></tr></table>';
$tables .= '<br />' x 2;
}
</script>
$tables
<customresponse id="0r0">
<answer type="loncapa/perl">
return 'SUBMITTED';
</answer>
</customresponse>
</problem>
--
Dr. Peter Dencker
wissenschaftl. Mitarbeiter
UNIVERSITÄT ZU LÜBECK
INSTITUT FÜR MATHEMATIK
Ratzeburger Allee 160
23562 Lübeck
Tel +49 451 500 4254
Fax +49 451 500 3373
dencker at math.uni-luebeck.de
www.math.uni-luebeck.de
More information about the LON-CAPA-users
mailing list