Arranging Numbers at Random / Boyan Mihaylov

Let’s say we want to arrange the numbers from 1 to 100 at random. This is a little confusing problem but there is a solution (not only one) for it. The basic way is the following: you have an array where you put your numbers, you generate a random number while this number is not contained in your array, then you add it to the array. Well, this method is very sluggish! When you add numbers to the array you decrease the size of the multitude of possible numbers. And when this size is too little, the while cycle loops very long until you get a random number, which is not already added to the array. Here is this example. I have used a stopwatch to count the necessary time for this method to finish.

iint count = 100;
ArrayList usedNumbers = new ArrayList(count);
Random rnd = new Random();
Stopwatch timer = new Stopwatch();
int num;

timer.Start();

while (usedNumbers.Count &amp;lt; count)
{
	do
	{
		num = rnd.Next(1, count + 1);
	}
	while (usedNumbers.Contains(num));

	usedNumbers.Add(num);
}

timer.Stop();
Console.WriteLine(timer.Elapsed);

iint count = 100;

ArrayList usedNumbers = new ArrayList(count);

Random rnd = new Random();

Stopwatch timer = new Stopwatch();

int num;

timer.Start();

while (usedNumbers.Count &lt; count)

{

num = rnd.Next(1, count + 1);

}

while (usedNumbers.Contains(num));

usedNumbers.Add(num);

}

timer.Stop();

Console.WriteLine(timer.Elapsed);

Here are my measurements with different count value.

100 numbers – 0.0005319 seconds
1000 numbers – 0.0567164 seconds
10000 numbers – 14.7841865 seconds

As you can see as the count value is bigger so the necessary time is much. Let’s have a look at another method, which solves the same problem. You put all numbers from 1 to 100 in an array (source numbers array). You generate a random index from 0 to 99, get this element from the source array and put it into destination array. Then the source array has 99 elements. Next time you generate a random index from 0 to 98, etc. This method is far better, because there are no such empty loops, in which you just loop until you get a number, which is not already taken. Here is the method and my measurements again.

ArrayList sourceNumbers = new ArrayList(count);
int index;

for (int i = 0; i < count; i++)
	sourceNumbers.Add(i + 1);

timer.Start();

while (usedNumbers.Count < count)
{
	index = rnd.Next(0, sourceNumbers.Count);

	num = (int)sourceNumbers[index];
	sourceNumbers.RemoveAt(index);

	usedNumbers.Add(num);
}

timer.Stop();
Console.WriteLine(timer.Elapsed);

ArrayList sourceNumbers = new ArrayList(count);

int index;

for (int i = 0; i < count; i++)

sourceNumbers.Add(i + 1);

timer.Start();

while (usedNumbers.Count < count)

{

index = rnd.Next(0, sourceNumbers.Count);

num = (int)sourceNumbers[index];

sourceNumbers.RemoveAt(index);

usedNumbers.Add(num);

}

timer.Stop();

Console.WriteLine(timer.Elapsed);

100 numbers – 0.0000673 seconds
1000 numbers – 0.0005855 seconds
10000 numbers – 0.0444583 seconds

As you can see this method is far faster then the first one. But it requires a little more memory to proceed.