Выберите случайный элемент, не зная общего количества элементов

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

List<string> items;
while (true)
{
    string item = GetNextItem();
    if (item == null)
        break;
}
int index = random.GetNext(0, items.count);

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

int index = -1;
int total;
string selectedItem;
while (true)
{
    string item = GetNextItem();
    if (item == null)
        break;

    ++total;
    int rnd = random.Next(0, total);
    if (rnd == total- 1)
    {
        index = total- 1;
        selectedItem = item;
    }
}

Это дает мне мой индексный номер и случайно выбранный элемент. Мое мышление в том, что, когда есть 3 общих элемента, например, я выбираю случайное число между 0 и 2 (включительно), и если он равен 2, я использую новый элемент как выбранный элемент, если не просто его игнорировать. По мере того как общее количество предметов увеличивается, каждый новый шанс выбора будет уменьшаться соответственно.

Является ли этот метод "хорошим"? Является ли это "случайным", как создание массива и выбор предмета позже? Это так быстро, как может быть? Прошу вас, по моему невежеству, в случайных числах.:)

Ответы

Ответ 1

То, что вы делаете, будет работать.

Здесь это повторение, которое может сделать алгоритм несколько более ясным:

Выберите первый элемент, есть 100% вероятность того, что это будет текущая выбор
Если есть второй элемент, есть шанс 1/2, это будет замените текущий выбор (если вы делаете математику, то это 50% шанс, что это будет первый элемент, и 50% шанс, что это будет второй элемент).
Если есть третий предмет, есть 1/3 шанс, что он заменит текущий выбор (опять же, математика вероятность для каждого элемента равна 1/3)
Если есть четвертый элемент, вероятность 1/4 он заменит текущий Выбор
... и т.д.

Обратите внимание, что вы можете вычислить шанс 1/x, сказав rand.Next(0,x) == 0 (или любое другое целое число между 0 и x - 1 включительно, вам не нужно беспокоиться об использовании total - 1.

На самом деле это довольно аккуратный подход; сначала я думал, что не будет никакого хорошего способа делать то, что вы просите!

Ответ 2

Ваш подход выглядит хорошо, да.

1 элемент = выбирается

2 предмета = 50% шанс выбрать второй предмет для замены 1-го

3 предмета = 33% шанс выбрать третий предмет, 67% шанс выбрать один из первых двух предметов

4 предмета = шанс 25% вы выбираете 4-й предмет, 75% шанс вы выбираете...

...

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

Вы можете упростить случайную проверку:

 int rnd = random.Next(0, total);
    if (rnd == 0)

Как неважно, какое из значений total-1 вы проверите для получения вероятности 1/n.

Ответ 3

мы можем доказать его индукцией. это верно для 1; если это верно для n; это верно для n + 1,
= > prob. выбора для первых n элементов = 1/n
= > sice prob. выбора (n + 1) -го элемента 1/(n + 1)
= > проблема выбора (n + 1) -го элемента n/(n + 1)
= > выборка для первых n элементов после добавления (n + 1) th element = 1/n * (n/n + 1) = 1/n + 1

Ответ 4

В вашем первом фрагменте кода вы используете items.count, поэтому знаете, сколько у вас элементов. Вам нужно знать этот номер, чтобы каждый элемент имел равные шансы на выбор.

Как вы писали, вы генерируете случайное число я такое, что 0 <= я < items.count, а затем вы попытаетесь быстро получить доступ к элементу я списка. (Связанный список может быть не лучшим выбором структуры данных.)

Если у вас есть хорошая оценка N количества элементов, вы можете использовать это вместо items.count.

Во втором фрагменте кода вам может потребоваться инициализировать "total" до нуля.