Conference rusure::math

You might try using something like the Shell Sort permutation, i.e. for the
largest power of 2, K, <= N, interchange all the elements that are K apart,
then all those K/2 apart, then K/3,... It's probably not necessary to 
interchange adjacent elements to get a reasonable degree of randomness.

Lynn 

Out of curiosity, what is wrong with random numbers?


				-- edp

There's no "problem" with random numbers or Lynn's algorithm in .1, except
they make an implicit assumption that all A[I] fits in memory or is fairly
quickly randomly accessed.

I would prefer a one-pass algorithm, so that the A[I] could be generated and
written out to magnetic tape in (say) 4K chunks.  So actual "shuffling" of
data would be quite difficult.

I keep thinking there's some approach, such as setting A[I] = f(i) mod N,
that does what I want.  I just don't know what the "f()" to do.  :-)

  John

You probably (no pun intended) want something like a linear congruential
random-number generator that cycles every n numbers.  See Knuth, volume 2:

Theorem A.  The linear congruential sequence:
		X(n+1) = (aX(n)+c) mod m
	has a period of length m if and only if:

    i) c is relatively prime to m;
   ii) b = a-1 is a multiple of p, for every p dividing m;
  iii) b is a multiple of 4, if m is a multiple of 4.

Of course, if you have a random number generator that generates the numbers
0..m-1 before cycling, and you just want the numbers 0..n-1 (where n < m),
you can use it, and just 'skip over' any numbers >= n.

It sounds like you have a 'toy' use for this.  So, just grab some numbers
that fit the above conditions, and let it fly.

Nijenhuis and Wilf (Combinatorial Algorithms), gives an algorithm
called RANPER, random permutation of n letters, on page 62.
However, I've looked at the algorithm and it does random interchanges,
which is not what you are looking for.

Oh, you want to do this for LARGE N. If you know in advance what N is, you
could try this: Find the largest p<N that is prime, and output
	  2
	(i + c) mod p	for i<p where c is some arbitrary constant
	i		for i>p

The numbers from p to N will appear in order, but all the others will be 
scrambled. You can, of course, rearrange p-N.

If you don't know in advance what N will be, but have an upper limit n for
N, then pick p>=n and output
	  2
	(i + c) mod p	if it's <N
	nothing		if it's >=N
for i = 1..p or until you have filled the array. (This may take a large
amount of time, but it's predictable.)

Lynn Yarbrough

Thanks, everybody.  I'm going to try Gilbert's .4 and see how well that works.

  John

Re 366.6:
          2
The set {i  mod p}, for prime p, doesn't contain p elements (except for p=2).
                                                      2        2
In fact, it contains at most (p+1)/2 elements, since x  = (p-x) , modulo p.

You're right, I should have said i*c1+c2 mod p. Of course, there are a lot
of other mappings that will work. - Lynn

			  i
If you generate the set {g  mod p} where g is a primitive root of a prime
p, it runs thru the integers 1 to (p-1), in some cases this could be a 
possbility.  The quadratic residue method only generates (p-1)/2
nonzero integers, though the sequence does have some nice properties
for digital signal processing (as does the primitive root sequence
here).

- Jim

OK, the linear congruential method is satisfactory for my purposes.  I should
note, however, that when 100 | N the rightmost digit forms a periodic sequence.
That is, they loop in a pattern 7,2,5,8,3,0,1,4,9,6 (for example).  This is
in fact a known property of linear-congruential random nuber generators -- the
rightmost digits (bits) aren't always very random.  I also tried the quadratic
congruential generator, where X(n+1) = d * X(n) ^ 2 + a * X(n) + c (mod N) which
I got from the same source.  It has the same problem with the right-hand digits.
This makes me wonder that for i | N, the digits (mod i) of the random sequence
aren't random if the random sequence is generated by any polynomial-version
congruential generator.  I suspect Knuth has that written down somewhere...

  John