выбрать случайный элемент из 2d массива с равной вероятностью

Question

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

 first element  1  9
 second element 7
 third element  10 3  2
 fourth element 6  92 14 73

Как выбрать элемент из этого 2d-массива с одинаковой вероятностью? Единственный очевидный способ выбрать случайный элемент из 2d - генерировать случайные числа и выбиратьстрока массива [first random] и генерирует секунду на основе размера этого элемента, но он не выбирает элемент с одинаковой вероятностью (например, второй элемент содержит 1 элемент, который будет иметь больше вероятностей, чем другие, 25% шанс, когда другие элементы имеют меньше, чем25%).Этот подход будет работать, если все элементы в первом слое имеют одинаковый размер массива, но не в этом случае.Я также считаю производительность (массив достаточно большой)

Answer 1

Почему бы просто не нормализовать его в одномерный массив?

Визуально, если ваш 2D массив выглядит так:

0:  X X
1:  X
2:  X X X
3:  X X X X

Думайте об этом так:

0: (X X) (X) (X X X) (X X X X)

Скобки просто добавлены для ясности, чтобы показать, что каждая строка оригинала объединяется в одну длинную строку.

Теперь вам просто нужно получить одно случайное число от 0 до N-1, где N - общее количество 'X на диаграмме.

Конечно, чтобы на самом деле получить доступ к выбранному случайному элементу, вам необходимо соответствующим образом пропустить 2D-массив (см. ответ Джеффа Свенсена ).

Answer 2

Я бы сгенерировал случайное число от 1 до всего количества элементов (10 в вашем примере). Затем пройдитесь по первому уровню вашего массива, отслеживая, сколько элементов вы уже встретили.

т.е. в псевдо:

randomNumber = rand(1,10)
soFar = 0
for(i=0, i<topLevel.size, i++)
  if ((soFar + topLevel[i].size) > randomNumber)
    return topLevel[i][randomNumber - soFar]
  else
    soFar += topLevel[i].size

Answer 3

Генерирует случайное число от 0 до (эксклюзивно) (#layer1+#layer2+#layer3+#layer4), где оператор # означает «количество элементов».Теперь, если случайное число находится между 0 и #layer1, верните layer1[randomnumber].Etcetera.

Итак, в основном, рассматривайте массив как один длинный одномерный массив.

Answer 4

Рассматривать коллекцию как длинный одномерный массив.Сгенерируйте случайное число от 0 до длины -1 этого массива.

Итак, в вашем примере у вас всего 10 элементов (0-9 при условии индексации по 0).Теперь у каждого предмета есть равные шансы на выбор.

Вам нужно будет либо рассчитать общее количество предметов, либо поддерживать его при добавлении / вычитании предметов.