Generating a sequence of unique random numbers
I need to generate a sequence of unique random numbers. I use a standard generator and get repetitions, and quite often, for example:
var rand = new Random();
for (var i = 0; i < 20; i++)
{
Console.Write(rand.Next());
Console.Write(' ');
}
1 3 3 2 0 9 5 8 2 4 9 ...
2
1 answers
Solution
There are 3 options: either you need to shuffle a sequence of numbers, or a little more complicated, or even more difficult)
Option #1
public static SpanExtensions
{
[ThreadStatic]
static readonly Random rand = new Random();
public static void Shuffle<T>(this Span<T> list)
{
var n = list.Count;
while (count > 1)
{
n--;
var k = rand.Next(n + 1);
T value = list[k];
list[k] = list[n];
list[n] = value;
}
}
}
Option #2
public static SpanExtensions
{
[ThreadStatic]
static readonly HashSet<int> usedNums = new HashSet<int>();
public static void NextDistinctSequence(this Random random, Span<int> buffer, int minValue = -1, int maxValue = -1)
{
// checks
if (buffer.IsEmpty) return;
usedNums.EnsureCapacity(buffer.Length);
for (var i < 0; i < buffer.Length; i++)
{
int num;
do
{
num = random.Next(minValue, maxValue);
} while (!usedNums.Add(num));
buffer[i] = num;
}
usedNums.Clear();
}
}
Just take and exclude the numbers already used from the sequence.
Option #3
It is based on the linear congruent method (reference #1)
public sealed class LcmRandom : Random
{
// fields
int cur;
public LcmRandom(int a, int c, int m, int divisor = 1, int remeinder = 0x7fff_ffff)
{
// init
cur = 1;
}
public LcmRandom(int divisor = 1, int remeinder = 0x4000_0000) :
this(1103515245, 12345, 0x4000_0000, divisor, remeinder) { } // gcc impl
public override int Next()
{
// checks
cur = (cur * a + c) % m;
return (cur / divisor) % remeinder;
}
}
Its joke is that if m & (m - 1) == 0
(i.e. m
is a power of 2), then this algorithm generates a sequence with the size of m
of unique numbers. I.e., you need to use it like this: change Random
-> LcmRandom
and that's it!
References
- Reference #1 - Wikipedia: Linear Congruent Method
1
Author: return, 2020-06-10 17:46:29