Select from a range but exclude certain numbers

Question

Is it possible to pick a random number from a given range (1-90), but exclude certain numbers. The excluded numbers are dynamically created but lets say they are 3, 8, and 80.

I have managed to create random number generator but couldn't identify any functions that let me fulfill my requirements.

Random r = new Random();
this.num = r.Next(1, 90);

The numbers which are to be excluded are previously generated numbers. So, if the random number is one, this would then get added to the excluded numbers list.

Answer 1

Using some handy extension methods here, you can create a range of numbers and select randomly from that rage. For example, with these extension methods:

public static T RandomElement(this IEnumerable<T> enumerable)
{
    return enumerable.RandomElementUsing(new Random());
}

public static T RandomElementUsing(this IEnumerable<T> enumerable, Random rand)
{
    int index = rand.Next(0, enumerable.Count());
    return enumerable.ElementAt(index);
}

You can apply these to a filtered range of numbers:

var random = Enumerable.Range(1, 90).Except(arrayOfRemovedNumbers).RandomElement();

Answer 2

Create a container which holds the numbers you do not want:

var excludedNumbers = new List<int> { 1, 15, 35, 89 };

Then use do something like:

Random random = new Random();

int number;

do
{
   number = r.Next(1, 90);
} while (excludedNumbers.Contains(number));

// number is not in the excluded list now

Answer 3

Might not be the best choice but you can use a while loop to check the numbers you don't want

Random r = new Random();
this.num = r.Next(1, 90);
do
{
    this.num = r.Next(1, 90);
}  
while (this.num == 3 || this.num == 8 || this.num == 90);

For much numbers you can use an array or a list and loop through them

int[] exclude = { 3, 8, 90, 11, 24 };
Random r = new Random();
this.num = r.Next(1, 90);
do
{
    this.num = r.Next(1, 90);
}
while (exclude.Contains(this.num));

Answer 4

Your latest update, which implies that each value can only be selected once, makes the problem easy.

1. Create a collection of values within the range.
2. Randomly shuffle the collection.
3. To"randomly" select an item, just return the first item in the collection, and remove it from the collection.

Answer 5

Random r = new Random();
this.num = r.Next(1, 90);

int excluded[] = new int[] { 3,8,80 }; // list any numbers in this array you want to exclude

for (int i = 0; i < excluded.Length; i++)
{
    if (this.num == excluded[i])
    {
        this.num = r.Next(1, 90); // or you can try doing something else here
    }
}

Answer 6

This solution does it in O(n) worst case where n is your list of exclusions, and constant memory. The code is a little longer but might be relevant if you:

• Possibly have a huge list of exclusions
• Need to run this many times
• Have a large range

It preserves the random distribution in the sense that it actually skips the exclusion list and generates a random number within the range excluding the set.

This is the implementation:

private static int RandomInRangeExcludingNumbers(Random random, int min, int max, int[] excluded)
{
    if (excluded.Length == 0) return random.Next(min, max);

    //array should be sorted, remove this check if you
    //can make sure, or sort the array before using it
    //to improve performance. Also no duplicates allowed
    //by this implementation
    int previous = excluded[0];
    for (int i = 1; i < excluded.Length; i++)
    {
        if (previous >= excluded[i])
        {
            throw new ArgumentException("excluded array should be sorted");
        }
    }

    //basic error checking, check that (min - max) > excluded.Length
    if (max - min <= excluded.Length)
        throw new ArgumentException("the range should be larger than the list of exclusions");

    int output = random.Next(min, max - excluded.Length);


    int j = 0;
    //set the start index to be the first element that can fall into the range
    while (j < excluded.Length && excluded[j] < min) j++;

    //skip each number occurring between min and the randomly generated number
    while (j < excluded.Length && excluded[j] <= output)
    {
        j++;
        output++;
        while (excluded.Contains(output))
            output++;
    }

    return output;
}

And a test function to make sure it works (over 100k elements)

private static void Test()
{
    Random random = new Random();
    int[] excluded = new[] { 3, 7, 80 };
    int min = 1, max = 90;

    for (int i = 0; i < 100000; i++)
    {
        int randomValue = RandomInRangeExcludingNumbers(random, min, max, excluded);

        if (randomValue < min || randomValue >= max || excluded.Contains(randomValue))
        {
            Console.WriteLine("Error! {0}", randomValue);
        }
    }
    Console.WriteLine("Done");
}

Answer 7

Make sure excludedNumbers is a HashSet for best performance.

var random = new Random();
var exludedNumbers = new HashSet<int>(new int[] { 3, 8, 80});
var randomNumber = (from n in Enumerable.Range(int.MinValue, int.MaxValue)
                    let number = random.Next(1, 90)
                    where !exludedNumbers.Contains(number)
                    select number).First();