[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