algorithm - 我怎样才能公平地从列表中选择一个项目？

Question

假设我有一份奖品 list :

A奖B奖C奖

并且，对于他们每个人，我想从我的与会者名单中抽出一名获胜者。

假设我的与会者名单如下:

用户 1、用户 2、用户 3、用户 4、用户 5

从该列表中选择用户的公正方式是什么？

显然，我将使用加密安全的伪随机数生成器，但如何避免偏向列表的前面？我假设我不会使用模数？

编辑
所以，这是我想出的:

class SecureRandom
{
    private RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();

    private ulong NextUlong()
    {
        byte[] data = new byte[8];
        rng.GetBytes(data);
        return BitConverter.ToUInt64(data, 0);
    }

    public int Next()
    {
        return (int)(NextUlong() % (ulong)int.MaxValue);
    }

    public int Next(int maxValue)
    {
        if (maxValue < 0)
        {
            throw new ArgumentOutOfRangeException("maxValue");
        }

        if (maxValue == 0)
        {
            return 0;
        }

        ulong chop = ulong.MaxValue - (ulong.MaxValue % (ulong)maxValue);

        ulong rand;

        do
        {
            rand = NextUlong();
        } while (rand >= chop);

        return (int)(rand % (ulong)maxValue);
    }
}

注意:

Next() 返回 [0, int.MaxValue] 范围内的整数
Next(int.MaxValue) 返回 [0, int.MaxValue) 范围内的整数

Answer 1

特殊随机数生成器的伪代码:

rng is random number generator produces uniform integers from [0, max)
compute m = max modulo length of attendee list
do {
    draw a random number r from rng
} while(r >= max - m)
return r modulo length of attendee list

这消除了列表前面部分的偏差。然后

put the attendees in some data structure indexable by integers
for every prize in the prize list
draw a random number r using above
compute index = r modulo length of attendee list
return the attendee at index

在 C# 中:

public NextUnbiased(Random rg, int max) {
    do {
        int r = rg.Next();
    } while(r >= Int32.MaxValue - (Int32.MaxValue % max));
    return r % max;
}

public Attendee SelectWinner(IList<Attendee> attendees, Random rg) {    
    int winningAttendeeIndex = NextUnbiased(rg, attendees.Length)
    return attendees[winningAttendeeIndex];
}

然后:

// attendees is list of attendees
// rg is Random
foreach(Prize prize in prizes) {
    Attendee winner = SelectWinner(attendees, rg);
    Console.WriteLine("Prize {0} won by {1}", prize.ToString(), winner.ToString());
}