Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

How do I make a random shuffle deterministic?

by Anonymous Monk
on Dec 05, 2012 at 16:20 UTC ( #1007319=perlquestion: print w/ replies, xml ) Need Help??
Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

I know how to randomly shuffle an array.

sub fisher_yates_shuffle { my $array = shift; my $i = @$array; while ( --$i ) { my $j = int rand( $i+1 ); @$array[$i,$j] = @$array[$j,$i]; } }

How can I rig the shuffle so that the results are always same on any given host but, random between different hosts?

Comment on How do I make a random shuffle deterministic?
Download Code
Re: How do I make a random shuffle deterministic?
by LanX (Canon) on Dec 05, 2012 at 16:25 UTC
    my best guess is:

    Initialize an array of random indices only once for each host.

    And use a host identifier (like hostname or ip) as seed in srand

    UPDATE:

    according to the docs (from perldoc -f srand) it's deterministic

    You can call srand($seed) with the same $seed to reproduce the same sequence from rand(), but this is usually reserved for generating predictable results for testing or debugging. Otherwise, donít call srand() more than once in your program.

    UPDATE: works fine:

    DB<100> srand 42 => 1 DB<101> rand => "0.744525000061007" DB<102> rand => "0.342701478718908" DB<103> rand => "0.111085282444161" DB<104> rand => "0.422338957988309" DB<105> srand 42 => 1 DB<106> rand => "0.744525000061007" DB<107> rand => "0.342701478718908" DB<108> rand => "0.111085282444161"

    Cheers Rolf

Re: How do I make a random shuffle deterministic?
by kennethk (Monsignor) on Dec 05, 2012 at 16:30 UTC

    Rigging the shuffle to be identical on a given host is easy -- simply feed a fixed seed to srand before your first call to rand.

    This makes variation between hosts easy by simply choosing a host-specific property as your seed -- perhaps a mangled hardware address?

    #!/usr/bin/perl -w use strict; use 5.10.0; my ($eth) = `ifconfig` =~ /HWaddr (\S+)/; $eth =~ s/\W//g; { no warnings 'portable'; srand hex $eth; } say rand for 1 .. 10;

    #11929 First ask yourself `How would I do this without a computer?' Then have the computer do it the same way.

Re: How do I make a random shuffle deterministic?
by davido (Archbishop) on Dec 05, 2012 at 16:37 UTC
Re: How do I make a random shuffle deterministic?
by Anonymous Monk on Dec 05, 2012 at 17:10 UTC

    Are there any faults in this?

    #!/usr/bin/perl use Sys::Hostname; sub seed { my $string = shift; my $seed; my @ascii = map ord, split //, $string; while ( <@ascii> ) { $seed += $_ }; srand $seed; } my $hostname = hostname; seed ( $hostname );
      Most implementations of "srand" take an integer and will silently truncate decimal numbers. This means "srand(42)" will usually produce the same results as "srand(42.1)". To be safe, always pass "srand" an integer.
      most strings will evaluate to 0 !
      DB<116> srand 0 => 1 DB<117> rand => "0.17082803610629" DB<118> rand => "0.749901980484964" DB<119> srand hostname => 1 DB<120> rand => "0.17082803610629" DB<121> rand => "0.749901980484964" DB<122> 0+ hostname => 0
      You need a checksum to produce a (pseudo) unique integer. You could try

      $seed += ord($_) for split //, hostname

      But whats wrong with the IP?

      Cheers Rolf

        The script has be as portable as possible. I'm not certain that the modules required to get an IP address will be available on an old version of perl that might be found on a Solaris or AIX host.

Re: How do I make a random shuffle deterministic?
by sundialsvc4 (Monsignor) on Dec 05, 2012 at 22:20 UTC

    Another possibility would be to keep, for each IP address, a shuffled list of numbers [1..n] if you see that you do not have one already for this IP.   Subsequent actual “shuffles” of the data would use the elements in this pre-shuffled list.   (Another way to say it is to capture the successive results from rand($i+1) as per the algorithm code-sample above, and re-use them.)   This has the possible advantage that it does not tamper with the (after all, global...) random-number seed value.   (Fiddling with the seed, of course, has a potential negative effect on other intended-to-be random sequences that your program might need to generate for other, unrelated purposes.   Capturing and re-using a sequence avoids this.   There might be another way to do it of which I am simply not aware.)

Re: How do I make a random shuffle deterministic?
by Anonymous Monk on Dec 07, 2012 at 03:14 UTC

    If your application relies on something random, provide your own random number generator. And do not consider using /dev/random as a source of random numbers for any game. Using /dev/random as a means of finding a seed for a random number generator is fine. As long as your program only requires one seed. There are lots of fast, not great random number generators out there. Use on of those for your game.

    I think the UUID will provide you the seed you want. There are Perl means of generating UUIDs that come from CGI requests and others.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1007319]
Approved by herveus
Front-paged by LanX
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (3)
As of 2014-08-21 05:05 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (127 votes), past polls