Могу ли я выбрать случайный элемент из набора, если я не знаю размер набора? - PullRequest
Новая
       34

Могу ли я выбрать случайный элемент из набора, если я не знаю размер набора?

3 голосов
/ 13 января 2011

Я пишу немного кода JavaScript, который должен выбирать случайный элемент на холсте, если элемент соответствует определенным требованиям. Существуют различные виды предметов (круги, треугольники, квадраты и т. Д.), И, как правило, не одинаковое количество предметов для каждого вида. Элементы расположены в иерархии (поэтому квадрат может содержать несколько кругов, а круг может содержать другие круги и т. Д. - все они могут быть вложенными).

Прямо сейчас мой (примитивный) подход к выбору случайного элемента заключается в следующем:

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

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

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

Кто-нибудь знает, как решить эту проблему?

Ответы [ 3 ]

5 голосов
/ 13 января 2011

Вы можете сделать это без предварительного создания списка (извините за мой псевдокод C) 

int index = 0;
foreach (element)
{
    if (element matches criteria)
    {
        index++;
        int rand = random value in [1 index] range
        if (1 == rand)
        {
            chosen = element;
        }
    }
}

Математика работает, скажем, у вас есть список, где 3 элемента соответствуют критериям, вероятностьпервый элемент будет выбран: 

1 * (1 - 1 / 2) * (1 - 1 / 3) = 1 * (1 / 2) * (2 / 3) = 1 / 3

Вероятность выбора второго элемента: 

(1 / 2) * (1 - 1 / 3) = (1 / 2) * (2 / 3) = 1 / 3

и, наконец, для третьего элемента 

1 / 3

Какой правильный ответ.

5 голосов
/ 13 января 2011

Начните с max_r = -1 и rand_node = null. Итерация по дереву. Для каждого узла, отвечающего критериям: 

r = random()
if r > max_r:
  rand_node = node
  max_r = r

В конце rand_node будет случайно выбранный узел, для которого требуется только одна итерация.

0 голосов
/ 13 января 2011

Вы можете сделать это рекурсивно:

  1. Пройти текущий уровень дерева, создав список
  2. Выбрать случайный узел из него (используя случайное число от 0 до списка. Длина)
  3. Повторяйте до тех пор, пока не доберетесь до конечного узла

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

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

...