Building a non sequential list of numbers (From a large range)

Question

I need to create a non sequential list of numbers that fit within a range. For instance i need to a generate a list of numbers from 1 to 1million and make sure that non of the numbers are in a sequential order, that they are completly shuffled. I guess my first question is, are there any good algorithms out there that could help and how best to implement this.

I currently am not sure the best way to implement, either via a c# console app that will spit out the numbers in an XML file or in a database that will spit out the numbers into a table or a set of tables, but that is really secondary to actually working out the best way of "shuffling" the set of numbers.

Any advice guys?

Rob

Answer 1

First off, if none of the numbers are in sequential order then every number in the sequence must be less than its predecessor. A sequence which has that property is sorted from biggest to smallest! Clearly that is not what you want. (Or perhaps you simply do not want any subsequence of the form 5, 6, 7 ? But 6, 8, 20 would be OK?)

To answer your question properly we need to know more information about the problem space. Things I would want to know:

1) Is the size of the range equal to, larger than, or smaller than the size of the sequence? That is, are you going to ask for ten numbers between 1 and 10, five numbers between 1 and 10 or fifty numbers between 1 and 10?

2) Is it acceptable for the sequence to contain duplicates? (If the number of items in the sequence is larger than the range, then clearly yes.)

3) What is the randomness being used for? Most random number generators are only pseudo-random; a clever attacker can deduce the next "random" number by knowing the previous ones. If for example you are generating a series of five cards out of a deck of 52 to make a poker hand, you want really strong randomness; you don't want players to be able to deduce what their opponents have in their hands.

Answer 2

How "non-sequential" do you want it?

You could easily generate a list of random numbers from a range with the Random class:

Random rnd1 = new Random();
List<int> largeList = new List<int>();

for (int i = 0, i < largeNumber, i++)
{
  largeList.Add(rnd1.Next(1, 1000001);
}

---

Edit to add

Admittedly the Durstenfeld algorithm (modern version of the Fisher–Yates shuffle apparently) is much faster:

var fisherYates = new List<int>(upperBound);
for (int i = 0; i < upperBound; i++)
{
  fisherYates.Add(i);
}

int n = upperBound;

while (n > 1)
{
   n--;
   int k = rnd.Next(n + 1);
   int temp = fisherYates[k];
   fisherYates[k] = fisherYates[n];
   fisherYates[n] = temp;
}

For the range 1 to 10000 doing a brute force "find a random number I've not yet used" takes around 4-5 seconds, while this takes around 0.001.

Props to Greg Hewgill for the links.

Answer 3

I understand, that you want to get a random array of lenth 1mio with all numbers from 1 to 1mio. No duplicates, is that right?

You should build up an array with your numbers ranging from 1 to 1mio. Then start shuffling. But it can happen (that is true randomness) that two ore even more numbers are sequential.

Have a look here

Answer 4

Here's a C# function to get you started:

public IEnumerable<int> GetRandomSequence(int max)
{
    var r = new Random();
    while (true)
    {
       yield return r.GetNext(max);
    }
}

call it like this to get a million numbers ranged 0-9999999:

var numbers = GetRandomSequence(9999999).Take(1000000);

As for sorting, or if you don't want to allow repeats, look at Enumerable.GetRange() (which will give you a consecutive ordered sequence) and use a Fisher-Yates (or Knuth) shuffle algorithm (which you can find all over the place).

Answer 5

"completly shuffled" is a very misunderstood term. One trick fraud experts use when examining what should be "random" data is to watch for cases where there no duplicate values (like 3743***88***123, because in a truly random sequence the chances of not having such a pair is very low... Exactly what are you trying to do ? What, exactly do you mean by "completly shuffled"? If all you mean is random sequence of digits, then just use the Random class in the CLR. to generate random numbers between 0 and 1M... as many as you need...

Answer 6

Well ,you could go with something like this (assuming that you want every number exactly once):

DECLARE @intFrom int
DECLARE @intTo int
DECLARE @tblList table (_id uniqueidentifier, _number int)

SET @intFrom = 0
SET @intTo = 1000000

WHILE (@intFrom < @intTo)
BEGIN
    INSERT INTO  @tblList
    SELECT       NewID(), @intFrom

    SET @intFrom = @intFrom + 1
END

SELECT    *  
FROM      @tblList
ORDER BY  _id

DISCLAIMER: I didn't test this, since I don't have an SQL Server at my disposal at the moment.

Answer 7

This may get you what you need:

1) Populate a list of numbers in order. If your range is 1 - x, it'll look like this: [1, 2, 4, 5, 6, 7, 8, 9, ... , x]

2) Loop over the list x times, each time choosing a random number between 0 and the length of your list - 1.

3) Use this chosen number to select the corresponding element from your list, and add this number to your output list.

4) Delete the element you just selected from your list. Rinse, repeat.

This will work for any range of numbers, not just lists that start with 1 or 0. The pseudocode looks like this:

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
shuffled_nums = []
for i in range(0, len(nums)):
    random_index = rand(0,len(nums))
    shuffled_nums.add(nums[random_index])
    del(nums[random_index])