Random Generation (with efficient exclusions)
Tags: csharp, dotnet, random, algorithms
Published: 2021-01-31 05:41:01

---
title: Random Generation (with efficient exclusions)
published: true
description: Algorithm analysis to dynamically choose the most efficient algorithm at runtime.
tags: csharp, dotnet, random, algorithm
//cover_image: https://direct_url_to_image.jpg
---

> Note: code examples are in C#, but the theory should be applicable to most programing languages

"How do I generate random numbers except for certain values?" - This is a relatively common question that I aim to answer with this post. I wrote some extension methods for the topic that look like this:

```cs
Random random = new();

int[] randomNumbers = random.Next(
    count: 5,
    minValue: 0,
    maxValue: 100,
    excluded: stackalloc[] { 50, 51, 52, 53 });

// if you want to prevent duplicate values
int[] uniqueRandomNumbers = random.NextUnique(
    count: 5,
    minValue: 0,
    maxValue: 100,
    excluded: stackalloc[] { 50, 51, 52, 53 });
```

There are two algorithms you can use:
1. **Pool Tracking:** you can dump the entire pool of possible values in a data structure (such as an array) and randomly generate indices of that data structure. [See Example Here](https://github.com/ZacharyPatten/Towel/blob/029cd81273fd08f16e73eed499bcc0f58319ebf2/Sources/Towel/Statics-Random.cs#L107)
2. **Roll Tracking:** you can track the values that that need to be excluded, reduce the range of random generation, and then apply an offset to the generated values. [See Example Here](https://github.com/ZacharyPatten/Towel/blob/029cd81273fd08f16e73eed499bcc0f58319ebf2/Sources/Towel/Statics-Random.cs#L41)

**Which algorithm is faster? It depends...**
Here are estimated runtime complexities of each algorithm:
1. **Pool Tracking:** `O(range + count + excluded)`
2. **Roll Tracking:** `O(count * excluded + excluded ^ 2)`

Notice how algorithm #1Pool Tracking is dependent on the range of possible values while algorithm #2 Roll Tracking is not. This means if you have a relatively large range of values, then algorithm #2 is faster, otherwise algorithm #1 is faster. So if you want the most efficient method, you just need to compare those runtime complexities based on the parameters and select the most appropriate algorithm. Here is what my "Next" overload currently looks like: [See Source Code Here](https://github.com/ZacharyPatten/Towel/blob/029cd81273fd08f16e73eed499bcc0f58319ebf2/Sources/Towel/Statics-Random.cs#L26)

```cs
public static void Next<Step, Random>(int count, int minValue, int maxValue, ReadOnlySpan<int> excluded, Random random = default, Step step = default)
	where Step : struct, IAction<int>
	where Random : struct, IFunc<int, int, int>
{
	if (count * excluded.Length + .5 * Math.Pow(excluded.Length, 2) < (maxValue - minValue) + count + 2 * excluded.Length)
	{
		NextRollTracking(count, minValue, maxValue, excluded, random, step);
	}
	else
	{
		NextPoolTracking(count, minValue, maxValue, excluded, random, step);
	}
}
```
Notes:
- I have included these extensions in a [Nuget Package](https://www.nuget.org/packages/Towel/1.0.23-alpha).
- I have [Benchmark Results Here](https://zacharypatten.github.io/Towel/articles/benchmarks.html#random-with-exclusions) and the [Benchmarks Source Code Here](https://github.com/ZacharyPatten/Towel/blob/master/Tools/Towel_Benchmarking/RandomWithExclusions.cs).
- I have another article on this topic (with graphs) here if interested: [Generating Unique Random Data](https://gist.github.com/ZacharyPatten/c9b43a2c9e8a5a5523883e77410f742d) _(but I wrote that before these overloads that allow exclusions)_

Specifically to point out one benchmark in particular:

``` ini

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.18363.1316 (1909/November2018Update/19H2)
Intel Core i7-4790K CPU 4.00GHz (Haswell), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=5.0.200-preview.20614.14
  [Host]     : .NET Core 5.0.2 (CoreCLR 5.0.220.61120, CoreFX 5.0.220.61120), X64 RyuJIT
  Job-JNMXTF : .NET Core 5.0.2 (CoreCLR 5.0.220.61120, CoreFX 5.0.220.61120), X64 RyuJIT

InvocationCount=1  UnrollFactor=1  

```
|                Method | MinValue | MaxValue |                Count |              Exclued |          Mean |       Error |        StdDev |        Median |
|---------------------- |--------- |--------- |--------------------- |--------------------- |--------------:|------------:|--------------:|--------------:|
|                 **Towel** |        **0** |  **1000000** | **1: sqrt(sqrt(range))** | **1: sqrt(sqrt(range))** |      **3.575 μs** |   **0.2149 μs** |     **0.6025 μs** |      **3.300 μs** |
|       HashSetAndArray |        0 |  1000000 | 1: sqrt(sqrt(range)) | 1: sqrt(sqrt(range)) |  6,172.451 μs | 128.1054 μs |   369.6132 μs |  6,091.300 μs |
| SetHashLinkedAndArray |        0 |  1000000 | 1: sqrt(sqrt(range)) | 1: sqrt(sqrt(range)) |  6,975.152 μs | 344.0002 μs | 1,014.2922 μs |  6,633.050 μs |
|  RelativelySimpleCode |        0 |  1000000 | 1: sqrt(sqrt(range)) | 1: sqrt(sqrt(range)) |            NA |          NA |            NA |            NA |

In that benchmark the range was `1,000,000` and the count was `sqrt(sqrt(1,000,000)) ~= 31` and the number of excluded values was `sqrt(sqrt(1,000,000)) ~= 31` so it is a rather extreme example but it demonstrates the difference between algorithm #1 (`3.575 μs`) and #2 (`6,172.451 μs`).

Thanks for reading. Feedback appreciated. :)