Hi Peter,
> The latter shows a remarkable imbalance.
> This seems to be a bias as it remains stable if choosing other randomisation.
The short answer is: the RNG is not well-fed the way you generate the seeds.
The bias results from the distribution of the “effective seeds”.
A better albeit not perfect (!!) way would be to add:
my @SEEDCHARS = split "",
q{abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!@#$%^&*()_+[];:'\"<>?,./};
sub gen_seed {
my $ret = "";
$ret .= $SEEDCHARS[random(0,$#SEEDCHARS, 1)] for (1..20);
return $ret;
}
and replace
my $seed = random( 1, 1E10, 1 );
with
my $seed = gen_seed();
You’ll notice that the resulting permutations are much more uniformly
distributed. (And you also might run into “code ran too long”).
Note: this approach is using knowledge about the implementation of the
underlying libraries.
The long answer will follow.
Stefan
On 31 Aug 2014, at 17:52, Peter Dencker <denc...@math.uni-luebeck.de> wrote:
>
> 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
> denc...@math.uni-luebeck.de
>
> www.math.uni-luebeck.de
> _______________________________________________
> LON-CAPA-users mailing list
> LON-CAPA-users@mail.lon-capa.org
> http://mail.lon-capa.org/mailman/listinfo/lon-capa-users
_______________________________________________
LON-CAPA-users mailing list
LON-CAPA-users@mail.lon-capa.org
http://mail.lon-capa.org/mailman/listinfo/lon-capa-users
