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 ...
Author: return, 2020-05-31

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

 1
Author: return, 2020-06-10 17:46:29