C# Random does not work like a random

Question

I have a graph, each node have 4 child nodes. I wrote a algorithm to generate a random path from a begin node to an end node. At each node, it chooses a random next node. Visited node can be revisited.

the code is like the following:

public List<Node> GetPath(Node begin, Node end)
{
    var nodes = new List<Node>();
    var node = begin;
    while (node != end)
    {
        nodes.Add(node);
        var next = node.Children[new Random().Next(4)];
        node = next;
    }

    nodes.Add(end);

    return nodes;
}

But sometimes, the Random does not work as expected. The "new Random().Next(4)" keeps generating 0. So it is always the first child node get chose and a very long repeat sequence like node1->node2->node1->node2... is generated and eventually an out of memory exception happens.

Is there a way to make the Random class works correctly?

possible duplicate of [Random number generator not working the way I had planned (C#)](http://stackoverflow.com/questions/767999/random-number-generator-not-working-the-way-i-had-planned-c) — Alexei Levenkov, Jul 24 '12 at 01:22

Glen Hughes · Accepted Answer · 2012-07-24T00:46:19.820

12

The reason is because Random is initialized based on the current time (there is no true random in computers... only psuedo-random). The while loop iterates too quickly, and the system time has not registered a change. So you're re-initializing a new Random object that starts with the same value.

Try creating one Random object that is reused throughout the method:

public List<Node> GetPath(Node begin, Node end)
{
    var nodes = new List<Node>();
    var node = begin;

    Random r = new Random();
    while (node != end)
    {
        nodes.Add(node);
        var next = node.Children[r.Next(4)];
        node = next;
    }

    nodes.Add(end);

    return nodes;
}

edited Jul 24 '12 at 00:46

answered Jul 24 '12 at 00:39

Glen Hughes

4,712
2
20
25

Thanks. This does solve the problem. But I got another issue. Actually I am calling this method in multi-threads to generate a bunch of paths. If use a Random outside the loop. A lot of same paths will be generated. I think it is because of the same reason why use new Random in loop generates very long sequence. – Ryan Jul 24 '12 at 01:06
1

@Ryan: if you're calling this several times in a loop, you should just use one `Random` per thread, preferably initialized based on the seed from a globally shared `Random` (note: `Random` is not thread-safe, so you'll need locking around the shared `Random`). – Jonathan Rupp Jul 24 '12 at 01:21

score 5 · Answer 2 · answered Jul 24 '12 at 00:38

Initialize Random instance outside loop, e.g.:

public List<Node> GetPath(Node begin, Node end)
{
    var nodes = new List<Node>();
    var node = begin;

    var random = new Random();

    while (node != end)
    {
        nodes.Add(node);
        var next = node.Children[random.Next(4)];
        node = next;
    }

    nodes.Add(end);

    return nodes;
}

Richard Schneider · Answer 3 · 2012-07-24T01:41:42.223

You mention that the method is being called upon in multiple threads. A solution is to have one random number generartor per thread that is seeded by a static rng.

I've also removed the constant 4 and changed it to node.Children.Count.

static Random seed = new Random();
[ThreadLocal] static Random rng;

public List<Node> GetPath(Node begin, Node end)
{
var nodes = new List<Node>();
var node = begin;

if (rng == null)
   rng = new Random(seed.Next());

while (node != end)
{
    nodes.Add(node);
    var next = node.Children[rng.Next(node.Children.Count)];
    node = next;
}

nodes.Add(end);

return nodes;
}

score 0 · Answer 4 · edited Jun 20 '20 at 09:12

There are a few things working against you here. The first is that you're expecting a different number every time you ask for one, but that's not what this class does nor is it the definition of random. So, this class is in fact working correctly.

Definition of Random

Made, done, happening, or chosen without method or conscious decision: "a random sample of 100 households".
Governed by or involving equal chances for each item.

Now, this class does its best at giving each option an equal opportunity at being chosen. So, when you think of random make sure you're putting into context the definition of the term. However, remember that this class does not work like the human mind.

Now, to address the fact that you're getting zero very frequently, it's happening for two reasons. First, you are creating a new Random class in every iteration. But more importantly, your range is too small because you're expecting it to give you a different number every time on a range of only 4 options, and since it's pseudo-random just as MSDN states you're getting the same answer frequently.

I realize the reason you're only giving it 4 options, but I think you might need to reconsider the type of functionality you're looking for because it would probably lead to less frustration.

C# Random does not work like a random

4 Answers4

Definition of Random

Related