Re: random generator for a given period
- From: "Jon Slaughter" <Jon_Slaughter@xxxxxxxxxxx>
- Date: Sun, 15 Feb 2009 03:15:08 -0600
"Andrei Alexandrescu" <SeeWebsiteForEmail@xxxxxxxxxx> wrote in message
news:KF2Fxt.17yI@xxxxxxxxxxxxxxxxxxxxxxxxxxx
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 once (and consequently
Rats. I meant "more than once", not "once". Apologies.
Andrei
Algorithm:
1. Find a few seeds that are "bijective" with a length of m. (that is they
shuffle the first m integers) Call it List_m. (note it is just an RNG with a
special seed... requires no memory) You might need to run the RNG a very
long time and keep not only the seed but an offset. m should be smaller than
the array you are applying it to.
Note basically all you did was find a permutation(this is really what you
seek). Unfortunately I don't think there is a way to sample the set of
permutations randomly without using memory.
2. Now apply List_m randomly to the array. That is, simply take a random
number and use it as an offset. This will shuffle the array starting at some
random point in it and shuffling the following m elements.
Of course your random offset cannot be random. You will need to get this
from another List_m
List1_m[i] + List2_k[i]
Basically you are composing permutations to get new permutations
List2_k only needs to have size n/m so that you can actually do
List1_m[i] + m*List2_k[i]
(basically partitions the list into m slices and "randomizes" each slice)
Suppose List1_m = 5 2 3 4 1
List2_k = 1 2
This means we can shuffle a set of size 10.
(remember, all the lists are actually special RNG's)
1 2 3 4 5 6 7 8 9 0
basically becomes
1 2 3 4 5 | 6 7 8 9 0
and the List_m is "applied" to each.
(List1_m[i] + m*List2_k[j]) mod n
and even choose random offsets such as
(List1_m[i] + m*List2_k[i]) + rnd) mod n
where rnd is chosen before you step through the list(it is in effect a
constant or "global" variable that doesn't change while the algorithm is in
use).
You can also apply list's to lists to shuffle them up. Remember, no memory
is used but just composing random number generators with special seeds. Of
course you do have to remember the seeds. The more "random" you want the
more seeds you'll need.
Of course the trade off is speed as rnd's are not fast. The more complex you
want the slower it gets.
You'll have to modify the algorithm to handle arbitrarily sized lists. Note
the algorithm tends to clump into groups of size m. Reapplying the
algorithm sufficiently many times should suffice.
1 - [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
2 - [12, 9, 8, 10, 11, 7, 6, 3, 2, 4, 5, 1, 18, 15, 14, 16, 17, 13]
3 - [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 1, 2]
4 - [8, 3, 1, 6, 10, 5, 2, 15, 13, 18, 4, 17, 14, 9, 7, 12, 16, 11]
100 - [1, 6, 14, 15, 5, 10, 13, 18, 8, 9, 17, 4, 7, 12, 2, 3, 11, 16]
You'll need to modify the algorithm to handle arbitrary sizes but it
probably will work fine. Remember that it is completely deterministic and no
memory is needed. You will have to modify the code so that this is the case.
To get better results you need to have r, the random offset, randomized but
not in the algorithm... only change it once you have completely stepped
through the enitre array. If you don't randomize r then you'll end up with
"clumps" of close numbers.
In any case it should get you started...
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace PermList
{
class Program
{
static int[] ListA = {6, 3, 2, 4, 5, 1 };
static int[] ListB = {1, 3, 2};
static int[] array;
static int s = 18;
static Random rnd = new Random();
static int r = rnd.Next() % s;
static int[] Shuffle(int[] array)
{
int sA = ListA.Count();
int sB = ListB.Count();
int[] A = new int[array.Count()];
r = rnd.Next(array[0]*array[1]*array[2]) % s;
int index;
for(int i = 0; i < s; i++)
{
int k = (int)Math.Floor((double)i / (double)sA);
index = ListA[i % sA] + sA*ListB[k] + r;
A[i] = array[(index-1) % s];
}
return A;
}
static void Main(string[] args)
{
array = new int[s];
for (int i = 0; i < s; i++)
array[i] = i+1;
Console.WriteLine("1 - " + ShowArray(array));
Console.WriteLine("2 - " + ShowArray(Shuffle(array)));
Console.WriteLine("3 - " + ShowArray(Shuffle(Shuffle(array))));
Console.WriteLine("4 - " + ShowArray(Shuffle(Shuffle(Shuffle(array)))));
for (int j = 0; j < 100; j++)
array = Shuffle(array);
Console.WriteLine("100 - " + ShowArray(Shuffle(Shuffle(Shuffle(array)))));
Console.ReadKey();
}
static string ShowArray(int[] array)
{
string ss = "[";
int kkk = Repeats(array);
if (kkk > 0)
ss = "R" + kkk.ToString() + "[";
int s = array.Count();
for (int i = 0; i < s - 1; i++)
ss += array[i].ToString() + ", ";
ss += array[s - 1].ToString() + "]";
return ss;
}
static int Repeats(int[] array)
{
int k = 0;
for (int i = 0; i < array.Count() - 1; i++)
for (int j = i + 1; j < array.Count(); j++)
if (array[i] == array[j])
k++;
return k;
}
}
}
.
- Follow-Ups:
- Re: random generator for a given period
- From: Andrei Alexandrescu
- Re: random generator for a given period
- References:
- random generator for a given period
- From: Andrei Alexandrescu
- Re: random generator for a given period
- From: Andrei Alexandrescu
- random generator for a given period
- Prev by Date: Re: -- partitioning a square into congruent rectangles
- Next by Date: Re: Q: divergent summation 1+2+5+10+21+...
- Previous by thread: Re: random generator for a given period
- Next by thread: Re: random generator for a given period
- Index(es):
Relevant Pages
|
