Генерация последовательности уникальных случайных чисел

Question

Мне нужно сгенерировать последовательность уникальных случайных чисел. Я использую стандартный генератор и получаю повторы, причём довольно часто, например:

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 ...

Answer 1

Решение

Тут 3 варианта: либо вам нужно шафлить последовательность чисел, либо немного посложнее, либо ещё сложнее)

Вариант #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;
        }
    }
}

Вариант #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();
    }
}

Просто берём и исключаем из последовательности уже используемые числа.

Вариант #3

Он основывается на линейном конгруэнтном методе (ссылка #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;
    }
}

Его прикол в том, что если m & (m - 1) == 0 (т. е. m – это степень 2-ки), то данный алгоритм генерирует последовательность размером в m из уникальных чисел. Т. е. его нужно использовать примерно вот так: меняете Random -> LcmRandom и всё!

Ссылки

Ссылка #1 – Wikipedia: Линейный конгруэнтный метод

БЛОГ НА HUSL