.NET抽奖算法

https://blog.csdn.net/farway000/article/details/124054507

https://www.linqpad.net/LINQPad6.aspx

T[] ShuffleCopy<T>(IEnumerable<T> data, Random r)
{
    var arr = data.ToArray();
    for (var i = arr.Length - 1; i > 0; --i)
    {
        int randomIndex = r.Next(i + 1);
        T temp = arr[i];
        arr[i] = arr[randomIndex];
        arr[randomIndex] = temp;
    }
    return arr;
}

int[] Measure(int n, int maxTime)
{
    var data = Enumerable.Range(1, n);
    var sum = new int[n];
    var r = new Random();
    for (var times = 0; times < maxTime; ++times)
    {
        var result = ShuffleCopy(data, r);
        for (var i = 0; i < n; ++i)
        {
            sum[i] += result[i] != i ? 1 : 0;
        }
    }
    return sum;
}


Util.Chart(
    Measure(10, 50_0000).Select((v, i) => new { X = i, Y = v}), 
    x => x.X, y => y.Y, Util.SeriesType.Bar
    ).Dump();

https://qa.1r1g.com/sf/ask/4000443051/

数组乱序算法常用于抽奖等生成临时数据操作。就拿年会抽奖来说，如果你的算法有任何瑕疵，造成了任何不公平，在年会现场 code review时，搞不好不能活着走出去。

这个算法听起来很简单，简单到有时会拿它做面试题去考候选人，但它实际又很不容易，因为细节很重要，稍不留神就错了。

首先来看正确的做法：

T[] ShuffleCopy<T>(IEnumerable<T> data, Random r)
{
    var arr = data.ToArray();
    for (var i = arr.Length - 1; i > 0; --i)
    {
        int randomIndex = r.Next(i + 1);
        T temp = arr[i];
        arr[i] = arr[randomIndex];
        arr[randomIndex] = temp;
    }
    return arr;
}

可以在 LINQPad6中，使用如下代码，测试随机打乱 0-10的数列，进行 50万条次模拟统计：

int[] Measure(int n, int maxTime)
{
    var data = Enumerable.Range(1, n);
    var sum = new int[n];
    var r = new Random();
    for (var times = 0; times < maxTime; ++times)
    {
        var result = ShuffleCopy(data, r);
        for (var i = 0; i < n; ++i)
        {
            sum[i] += result[i] != i ? 1 : 0;
        }
    }
    return sum;
}

然后可以使用 LINQPad特有的报表函数，将数据展示为图表：

Util.Chart(
    Measure(10, 50_0000).Select((v, i) => new { X = i, Y = v}), 
    x => x.X, y => y.Y, Util.SeriesType.Bar
    ).Dump();

运行效果如下（记住这是正确的示例）：

0810dd346f2480b1a985a8f3bb01d28b.png

可见 50万次测试中，曲线基本平稳， 0-10的分布基本一致，符合统计学上的概率相等。

再来看看如果未做任何排序的代码：

T[] ShuffleCopy<T>(IEnumerable<T> data, Random r) => data.ToArray();