Как я могу честно выбрать элемент из списка?

Question

Допустим, у меня есть список призов:

PrizeA PrizeB PrizeC

И для каждого из них я хочу выбрать победителя из списка моих участников.

Дайте, чтобы мой список участников был следующим:

пользователь1, пользователь2, пользователь3, пользователь4, пользователь5

Какой непредвзятый способ выбрать пользователя из этого списка?

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

EDIT
Итак, вот что я придумал:

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);
    }
}

BEWARE:

Next() Возвращает int в диапазоне [0, int.MaxValue]
Next(int.MaxValue) Возвращает int в диапазоне [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());
}

Answer 2

Вам уже показалось несколько совершенно хороших ответов, которые зависят от знания длины списка заранее.

Чтобы честно выбрать один элемент из списка без , для начала нужно знать длину списка:

 if (list.empty()) error_out_somehow
 r=list.first()          // r is a reference or pointer
 s=list.first()          // so is s
 i = 2
 while (r.next() is not NULL)
    r=r.next()
    if (random(i)==0) s=r  // random() returns a uniformly
                           // drawn integer between 0 and i
    i++
 return s

(полезно, если ваш список хранится как связанный список)

---

Чтобы распределить призы в этом сценарии, просто пройдите по списку призов, выбирая случайного победителя для каждого. (Если вы хотите предотвратить двойной выигрыш, удалите победителя из списка участников.)

---

Почему это работает?

1. Вы начинаете с первого элемента в 1/1
2. На следующем проходе вы выбираете второй элемент наполовину (1/2), что означает, что первый элемент имеет вероятность 1 * (2-1)/2 = 1/2
3. на дальнейших итерациях вы выбираете n-й предмет с вероятностью 1/n, и вероятность каждого предыдущего предмета уменьшается в (n-1)/n

, что означает, что когда вы подходите к концу, вероятность наличия m-го элемента в списке (из n элементов) составляет

1/m * m/(m+1) * (m+1)/(m+2) * ... * (n-2)/(n-1) * (n-1)/n = 1/n

и одинаково для каждого предмета.

---

Если вы обратите внимание, вы заметите, что это означает обход всего списка каждый раз, когда вы хотите выбрать элемент из списка, так что это не максимально эффективно для (скажем) переупорядочения всего списка (хотя это и делает это справедливо).

Answer 3

Предполагая, что генератор случайных чисел достаточно распределен ...

do {
    i = rand();
} while (i >= RAND_MAX / 5 * 5);
i /= 5;

Это дает каждый из 5 слотов

[0 .. RAND_MAX / 5)
[RAND_MAX / 5 .. RAND_MAX / 5 * 2)
[RAND_MAX / 5 * 2 .. RAND_MAX / 5 * 3)
[RAND_MAX / 5 * 3 .. RAND_MAX / 5 * 4)
[RAND_MAX / 5 * 4 .. RAND_MAX / 5 * 5)

и сбрасывает рулон, который выпадает из диапазона.

Answer 4

Вы можете на 100% надежно выбрать случайный элемент из любого произвольного списка за один проход, не зная заранее, сколько элементов в списке.

Код Psuedo:

count = 0.0;
item_selected = none;

foreach item in list
 count = count + 1.0;
 chance = 1.0 / count;
 if ( random( 1.0 ) <= chance ) then item_selected = item;

Тестовая программа, сравнивающая результаты одного rand ()% N с итерациями, как указано выше:

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

static inline float frand01()
{
    return (float)rand() / (float)RAND_MAX;
}

int _tmain(int argc, _TCHAR* argv[])
{
    static const int NUM_ITEMS = 50;

    int resultRand[NUM_ITEMS];
    int resultIterate[NUM_ITEMS];

    memset( resultRand, 0, NUM_ITEMS * sizeof(int) );
    memset( resultIterate, 0, NUM_ITEMS * sizeof(int) );

    for ( int i = 0; i < 100000; i++ )
    {
        int choiceRand = rand() % NUM_ITEMS;

        int choiceIterate = 0;
        float count = 0.0;
        for ( int item = 0; item < NUM_ITEMS; item++ )
        {
            count = count + 1.0f;
            float chance = 1.0f / count;
            if ( frand01() <= chance )
            {
                choiceIterate = item;
            }
        }

        resultRand[choiceRand]++;
        resultIterate[choiceIterate]++;
    }

    printf("Results:\n");
    for ( int i = 0; i < NUM_ITEMS; i++ )
    {
        printf( "%02d - %5d %5d\n", i, resultRand[i], resultIterate[i] );
    }

    return 0;
}

Выход:

Results:
00 -  2037  2050
01 -  2038  2009
02 -  2094  1986
03 -  2007  1953
04 -  1990  2142
05 -  1867  1962
06 -  1941  1997
07 -  2023  1967
08 -  1998  2070
09 -  1930  1953
10 -  1972  1900
11 -  2013  1985
12 -  1982  2001
13 -  1955  2063
14 -  1952  2022
15 -  1955  1976
16 -  2000  2044
17 -  1976  1997
18 -  2117  1887
19 -  1978  2020
20 -  1886  1934
21 -  1982  2065
22 -  1978  1948
23 -  2039  1894
24 -  1946  2010
25 -  1983  1927
26 -  1965  1927
27 -  2052  1964
28 -  2026  2021
29 -  2090  1993
30 -  2039  2016
31 -  2030  2009
32 -  1970  2094
33 -  2036  2048
34 -  2020  2046
35 -  2010  1998
36 -  2104  2041
37 -  2115  2019
38 -  1959  1986
39 -  1998  2031
40 -  2041  1977
41 -  1937  2060
42 -  1946  2048
43 -  2014  1986
44 -  1979  2072
45 -  2060  2002
46 -  2046  1913
47 -  1995  1970
48 -  1959  2020
49 -  1970  1997

Answer 5

Без действительно случайных битов вы всегда будете иметь некоторую предвзятость. Количество способов назначить призы гостям намного больше, чем у любого распространенного периода PRNG даже для довольно небольшого числа гостей и призов. В соответствии с предложением lpthnc, купите несколько действительно случайных бит или оборудование для генерации случайных битов.

Что касается алгоритма, просто выполните случайное перемешивание списка гостей. Будьте осторожны, так как наивные алгоритмы тасования имеют смещение: http://en.wikipedia.org/wiki/Shuffling#Shuffling_algorithms

Answer 6

Здесь вы найдете обсуждение Олегом Киселевым чисто функциональной случайной перетасовки.

Описание связанного контента (цитируется в начале этой статьи):

Эта статья даст две чисто функциональные программы, которые отлично , случайно и равномерно перемешать последовательность произвольных элементов. Мы докажите, что алгоритмы верны. Алгоритмы реализованы в Haskell и может быть тривиально переписан в другой (функциональный) языки. Мы также обсуждаем, почему обычно используется сортировка на основе шаффла Алгоритм не дотягивает до идеального тасования.

Вы можете использовать это, чтобы перетасовать свой список, а затем выбрать первый элемент перетасованного результата (или, может быть, вы предпочитаете не давать два приза одному и тому же человеку, а затем использовать n начальных позиций результата, для n = количество призов); или вы могли бы упростить алгоритм, чтобы просто произвести первый элемент; или вы можете осмотреть этот сайт, потому что я мог бы поклясться, что есть статья о выборе одного случайного элемента из произвольной древовидной структуры с равномерным распределением, чисто функциональным способом, с предоставленным доказательством правильности, но мой поиск-фу подводит меня, и я не могу найти его.

Answer 7

Вы можете купить действительно случайные биты у поставщика или использовать механическое устройство.

Answer 8

Если вы используете хороший генератор чисел, даже с модулем ваше смещение будет минимальным. Например, если вы используете генератор случайных чисел с 64-битной энтропией и пятью пользователями, ваше смещение к передней части массива должно быть порядка 3x10 ^ -19 (мои числа могут быть отключены Не думаю, что много). Это дополнительная вероятность 3-в-10-квинтиллионов выигрыша первого пользователя по сравнению с более поздними пользователями. Это должно быть достаточно хорошо, чтобы быть справедливым в чьей-либо книге.

Answer 9

Полагаю, что одним из ответов было бы присвоение каждому элементу случайного значения и выборка наибольшего или наименьшего значения при необходимости.

Я не уверен, что это наиболее эффективно, хотя ...