[LON-CAPA-users] random_permutation, choosing the $seed

Stefan Dröschler st.droeschler at ostfalia.de
Mon Sep 1 06:45:53 EDT 2014


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 <dencker at 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
>    dencker at math.uni-luebeck.de
> 
>    www.math.uni-luebeck.de
> _______________________________________________
> LON-CAPA-users mailing list
> LON-CAPA-users at mail.lon-capa.org
> http://mail.lon-capa.org/mailman/listinfo/lon-capa-users



More information about the LON-CAPA-users mailing list