Ensure uniform (ish) distribution with random number generation

Question

I have a list of objects and I would like to access the objects in a random order continuously.

I was wondering if there was a way of ensuring that the random value were not always similar.

Example.

My list is a list of Queues, and I am trying to interleave the values to produce a real-world scenario for testing.

I don't particularly want all of the items in Queues 1 and 2 before any other item. Is there a guaruanteed way to do this?

Thanks

EDIT :: The List of Queues I have is a basically a list of files that i am transmitting to a webservice. Files need to be in a certain order hence the Queues.

So I have Queue1 = "set1_1.xml", set1_2.xml", ... "set1_n.xml" Queue2 ... ... QueueN

While each file needs to be transmitted in order in terms of the other files in its queue, I would like to simulate a real world simulation where files would be received from different sources at different times and so have them interleaved.

At the moment I am just using a simple rand on 0 to (number of Queues) to determine which file to dequeue next. This works but I was asking if there might have been away to get some more uniformity rather than having 50 files from Queue 1 and 2 and then 5 files from Queue 3.

I do realise though that altering the randomness no longer makes it random.

Thank you for all your answers.

Answer 1

Well, it isn't entire clear what the scenario is, but the thing with random is you never can tell ;-p. Anything you try to do to "guarantee" thins will probably reduce the randomness.

How are you doing it? Personally I'd do something like:

static IEnumerable<T> GetItems<T>(IEnumerable<Queue<T>> queues)
{
    int remaining = queues.Sum(q => q.Count);
    Random rand = new Random();
    while (remaining > 0)
    {
        int index = rand.Next(remaining);
        foreach (Queue<T> q in queues)
        {
            if (index < q.Count)
            {
                yield return q.Dequeue();
                remaining--;
                break;
            }
            else
            {
                index -= q.Count;
            }
        }
    }
}

This should be fairly uniform over the entire set. The trick here is that by treating the queues as a single large queue, the tendency is that the queue's with lots of items will get dequeued more quickly (since there is more chance of getting an index in their range). This means that it should automatically balance consumption between the queues so that they all run dry at (roughly) the same time. If you don't have LINQ, just change the first line:

int remaining = 0;
foreach(Queue<T> q in queues) {remaining += q.Count;}

Example usage:

static void Main()
{
    List<Queue<int>> queues = new List<Queue<int>> {
        Build(1,2,3,4,5), Build(6,7,8), Build(9,10,11,12,13)
    };
    foreach (int i in GetItems(queues))
    {
        Console.WriteLine(i);
    }
}
static Queue<T> Build<T>(params T[] items)
{
    Queue<T> queue = new Queue<T>();
    foreach (T item in items)
    {
        queue.Enqueue(item);
    }
    return queue;
}

Answer 2

It depends on what you really want...

If the "random" values are truly random then you will get uniform distribution with enough iterations.

If you're talking about controlling or manipulating the distribution then the values will no longer be truly random!

So, you can either have:

• Truly random values with uniform distribution, or
• Controlled distribution, but no longer truly random

Answer 3

Are you trying to shuffle your list?

If so you can do it by sorting it on a random value.

Try something like this:

private Random random = new Random();
public int RandomSort(Queue q1, Queue q2)
{
  if (q1 == q2) { return 0; }
  return random.Next().CompareTo(random.Next());
}

And then use the RandomSort as the argument in a call to List.Sort();

Answer 4

If the items to be queued have a GetHashCode() algorithm which distributes values evenly across all integers, you can take the modulus operator on the hash value to specify which queue to add the item to. This is basically the same principle which hash tables use to assure an even distribution of values.