Re: random generator for a given period

On 2009-02-15 01:35:28 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@xxxxxxxxxx> said:

Allen McIntosh wrote:
Andrei Alexandrescu wrote:
I've looked into the problem of randomly covering an array. Given an
array of length m, generate a succession of m random indices into that
array such that the same index is never visited more than once (and consequently the entire array is visited in m steps). So what I'm looking for is a random numbers generator of a given period and with the range equal to the period.

It sounds like what you need is a random permutation. The Wikipedia article on "random permutation" should get you started.

If you are using this for anything serious, you should read
http://www.cigital.com/papers/download/developer_gambling.php
(google "computer shuffle card deck" for more)

I am familiar with shuffling via e.g. the Fisher-Yates algorithm. However I am not looking for that. The original array is supposed to remain untouched, I just need to generate a random sequence of indices to walk it. Again, a simple approach is to generate a separate array of indices and shuffle that. But I'd like to do it in constant space, e.g. by using a special random number generator.


Andrei

If you literally want a pseudo random number generator with an arbitrary user specified
length implelemented with the usual modular arithmetic you will find that things are
very awkward technically as most modulii will be composite with multiple distinct
prime factors. The usual theory covers prime or prime power modulus only as these
lead to very tractable finite groups with only a few subgoups. (That is why the
seed for use with prime power is restricted. It picks the desired subgroup!) You can
keep track of the subgroups but that requires bookkeeping that looks more like
log n space.

If development time is at all valued the use of a conventional permutation algorithm
with a marker array would seem sensible. Memory is very chearp anymore except for
folks doing rather special hardware.




.

Relevant Pages

  • Re: Randomly outputting an array
    ... This describes a random permutation. ... INT is generic and accepts any numeric input (e.g., ... from reals and complex numbers of any kinds ... You can rewrite it to work with any type array that you need. ...
    (comp.programming)
  • Re: BASIC programming, random# and arrays.
    ... you'll try to get a random permutation of given data. ... Alternatively, roll a random number x in 1..n-m, where m is the number of items drawed already, and then advance in the array to the x-th not yet drawn element. ...
    (comp.sys.atari.8bit)
  • Re: Sample Function / Random Permutations (newbie)
    ... Roland Rau wrote: ... > After giving an array of n integers ranging from 1 to n, ... > This is similar to take a random permutation of that array and then ...
    (comp.lang.c)
  • Re: random generator for a given period
    ... array such that the same index is never visited more than once. ... So what I'm looking for is a random numbers generator of a given period and with the range equal to the period. ... The Wikipedia article on "random permutation" should get you started. ... (google "computer shuffle card deck" for more) ...
    (sci.stat.math)
  • Re: random generator for a given period
    ... Andrei Alexandrescu wrote: ... array of length m, generate a succession of m random indices into that array such that the same index is never visited once (and consequently ...
    (sci.math)