How do I make a random shuffle deterministic?

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Replies are listed 'Best First'.
Re: How do I make a random shuffle deterministic? by davido (Cardinal) on Dec 05, 2012 at 16:37 UTC
It seems that you should be able to seed using the integer representation of the host's IP address, or an integer representation of the characters from the hostname, and end up with stable results. An aside: I was just reading this last night, for no good reason: Fisher Yates Shuffle: Pseudoraondom Generators: Problems involving state space, seeding, and usage. I'm not convinced that Perl's randomness generator is free from this issue, which would make your Fisher Yates shuffle (as well as the one included with List::Util suspect. Hopefully someone can settle this concern. But reading Algorithm::Numerical::Shuffle's POD confirms that implementations using rand may have a flaw. Dave	[reply]
Re: How do I make a random shuffle deterministic? by LanX (Saint) 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"` [download] Cheers Rolf	[reply] [d/l]
Re: How do I make a random shuffle deterministic? by kennethk (Abbot) 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; [download] #11929 First ask yourself `How would I do this without a computer?' Then have the computer do it the same way.	[reply] [d/l]
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 );` [download]	[reply] [d/l]
Re^2: How do I make a random shuffle deterministic? by LanX (Saint) on Dec 05, 2012 at 17:15 UTC
`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` [download] 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	[reply] [d/l] [select]
Re^3: How do I make a random shuffle deterministic? by Anonymous Monk on Dec 05, 2012 at 17:32 UTC
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.	[reply]
Re^4: How do I make a random shuffle deterministic? by LanX (Saint) on Dec 05, 2012 at 17:37 UTC
Re^5: How do I make a random shuffle deterministic? by Anonymous Monk on Dec 05, 2012 at 17:46 UTC
Some notes below your chosen depth have not been shown here
Re^5: How do I make a random shuffle deterministic? by Anonymous Monk on Dec 06, 2012 at 15:07 UTC
Some notes below your chosen depth have not been shown here
Re^4: How do I make a random shuffle deterministic? by DrHyde (Prior) on Dec 06, 2012 at 11:58 UTC
Re: How do I make a random shuffle deterministic? by sundialsvc4 (Abbot) 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.	[reply]


Perl Monk, Perl Meditation
	PerlMonks