Выберите случайный объект, не зная общее количество объектов
У меня есть случай, где я должен выбрать случайный объект, но я не знаю общее количество объектов, и я не хочу создавать огромный массив, затем выбирают объект. Например, это - то, что я имею прямо сейчас:
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, я использую новый объект в качестве выбранного пункта, если не просто игнорируют его. Как общее количество увеличений объектов, шанс каждого нового объекта того, чтобы быть выбранным уменьшается соответственно.
Действительно ли этот метод "Хорош"? Действительно ли это столь же "случайно" как создание массива и выбирание объект позже? Это с такой скоростью, как это может быть? Ведите меня через мое незнание в случайных числах.:)
4 ответа
То, что вы делаете, будет работать.
Вот его повторение, которое может немного прояснить алгоритм:
- Выберите первый элемент, есть 100% шанс, что это будет текущий выбор
- Если есть второй элемент, с вероятностью 1/2 он заменит текущий выбор (если вы выполните математические вычисления, то с вероятностью 50% это будет первый элемент, и с вероятностью 50% это будет второй элемент)
- Если есть третий элемент, с вероятностью 1/3 он заменит текущий выбор (опять же, математическая вероятность для каждого элемента равна 1/3)
- Если есть четвертый элемент, с вероятностью 1/4 он заменит текущий {{1} }} selection
- ... etc ...
Обратите внимание, что вы можете вычислить вероятность 1 / x , сказав rand.Next (0, x) == 0 (или любое другое целое число от 0 до x - 1 включительно; вам не нужно беспокоиться об использовании total - 1 .
На самом деле это довольно изящный подход. Но не было никакого хорошего способа сделать то, о чем вы просили!
В первом фрагменте кода вы используете items.count, поэтому вы знаете, сколько у вас элементов. Вам необходимо знать это число, чтобы каждый элемент имел равные шансы быть выбранным.
Как вы писали, вы генерируете случайное число i такое, что 0 <= i Если у вас есть хорошая оценка N количества элементов, вы можете использовать это вместо items.count. Во втором фрагменте кода вам, возможно, придется инициализировать «total» равным нулю.
Ваш подход выглядит хорошо, да.
1 предмет = выбирается
2 предмета = 50% вероятность того, что вы выберете 2-й предмет вместо 1-го
3 предмета = 33% вероятность того, что вы выберете 3-й предмет, 67% вероятность того, что вы выберете один из первых двух предметов
4 предмета = 25% вероятность того, что вы выберете 4-й предмет, 75% вероятность того, что вы выберете ...
...
Таким образом, вопреки большинству других ответов здесь, я думаю, что у вас есть рабочее решение, которое дает равномерное распределение вероятности.
Вы можете упростить случайную проверку:
int rnd = random.Next(0, total);
if (rnd == 0)
Поскольку не имеет значения, на какое из значений total-1 вы проверяете, чтобы получить вероятность 1/n.
мы можем доказать это по индукции.
это верно для 1;
если это верно для n; это верно для n + 1;
=> проблема. выбора для первых n элементов = 1 / n
=> sice проблема. выбора (n + 1) -го элемента равно 1 / (n + 1)
=> вероятность того, что не выбран (n + 1) -й элемент, равна n / (n + 1)
=> вероятность выбора первых n элементов после добавления (n + 1) -го элемента = 1 / n * (n / n + 1) = 1 / n + 1