C # Правильно ли я делаю "Рандомизацию заливов и Дарема путём перемешивания"? - PullRequest
Новая
       16

C # Правильно ли я делаю "Рандомизацию заливов и Дарема путём перемешивания"?

4 голосов
/ 01 июня 2019

Я попытался импровизировать генератор случайных чисел, используя алгоритм «Рандомизация заливов и Дарема по тасованию».Я следовал учебному пособию онлайн и сделал этот код: 

 public int[] GenerateRandomSequence_Improved(int n, int min, int max)
 {
       int[] seq = new int[n];
       for(int i = 0; i < n; i++)
       {
           int rand = GenerateNextRandomNumber(min, max);

           rand = min + rand % (max + 1 - min);
           seq[i] = rand;
       }
       return seq;
 }

Я хочу знать, правильно ли я это сделал или нет ..

РЕДАКТИРОВАТЬ: Это код для метода GenerateNextRandomNumber 

public int GenerateNextRandomNumber(int min, int max)
{
       return cSharpRNG.Next(min,max);
}

Ответы [ 2 ]

1 голос
/ 02 июня 2019

Согласно Кнуту TAOCP Vol.2 стр.34 Алгоритм B, правильный алгоритм следующий: 

public class BaysDurham
{
    private readonly int[] t;
    private int y;      // auxiliary variable

    // Knuth TAOCP Vol. 2 p. 34 Algorithm B

    public BaysDurham(int k)
    {
        t = new int[k];

        for (int i = 0; i < k; i++)
        {
            t[i] = rand.Next();
        }

        y = rand.Next();
    }

    public int Next()
    {
        var i = (int)((t.Length * (long) y) / int.MaxValue);   // mitigates the bias
        y = t[i];
        t[i] = rand.Next();
        return y;
    }

    private readonly Random rand = new Random();
}

Я позволяю вам адаптировать диапазон выходных данных, но просто знаю, что формула, которую вы используете с модулем, вносит существенное смещение и делает распределение неформа пожалуйста, посмотрите на это .

1 голос
/ 02 июня 2019

Вот что я считаю правильной реализацией перетасовки Бэйса-Дарема. Предупреждение о смещении в индексации из-за операции по модулю верно.

.NET Core 2.2, x64 Win10 

using System;
using System.Diagnostics;

namespace BaysDurhamShuffling
{
    public class BaysDurhamRNG
    {
        public int[] _table;
        public int   _xnext;

        public Random _rng = null;

        public BaysDurhamRNG(int n, int seed = 312357) {
            Debug.Assert(n > 1);

            _rng = new Random(seed);
            _table = new int [n];
            for(int k = 0; k != n; ++k) {
                _table[k] = _rng.Next();
            }
            _xnext = _rng.Next();
        }

        public int next() {
            var x = _xnext; // store return value

            var j  = _xnext % _table.Length; // form the index j into the table
            _xnext = _table[j];              // get jth element of table and to copy it to the output stream on next call
            _table[j] = _rng.Next();         // replace jth element of table with next random value from input stream

            return x; // return what was stored in next value
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var rng = new BaysDurhamRNG (16, 12345);

            for(int k = 0; k != 30; ++k) {
                var x = rng.next();
                Console.WriteLine($"RV = {x}");
            }
        }
    }
}
...