Процентная вероятность логики проблема / рефакторинг (JavaScript)

Question

У меня есть массив чисел, каждое из которых представляет вес. числа в массиве находятся в диапазоне от 0 до 1, и общее количество этих чисел составляет 1. Таким образом, если скажем, что массив [1] равен 0,6, то это означает, что я хочу, чтобы он показывался примерно в 60% случаев. Сам массив мне не известен, поэтому я не знаю этих чисел, например, они вводятся пользователем.

У меня есть решение, которое будет работать, но я не знаю, является ли это наиболее эффективным способом сделать это. Мое решение кажется очень неэффективным. Вот оно

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

это похоже на большую работу, есть ли более простое решение? моя голова не вращается так быстро

РЕДАКТИРОВАТЬ - исходный массив никак не сортируется

РЕДАКТИРОВАТЬ 2 - В основном у меня возникают проблемы при сравнении этого случайного числа с несортированным массивом. Мне нужно, чтобы несортированные остались неизменными, поэтому я создал этот новый массив в своей логике

Answer 1

Если у вас есть массив, элементы которого равны 1, вы можете использовать следующий алгоритм:

1. Выберите равномерно распределенное (псевдо) случайное число r между 0 и суммой весов..
2. Для каждого веса:
   • Если r меньше веса, выберите его и выйдите.
   • В противном случае вычтите вес из r, так что теперь он находится между 0 исумма оставшихся весов.

Поскольку r всегда находится между 0 и суммой оставшихся весов, всегда существует вероятность, пропорциональная каждому весу, что r меньшеэто когда цикл достигает этого веса.

В JavaScript:

var weights = [0.5, 0.15, 0.3, 0.05];
var index = weights.length - 1;  // Last by default to avoid rounding error.
var r = Math.random();

for (var i = 0; i < a.length - 1; ++i) {
  if (weights[i] > r) { index = i; break; }
  // The rest of the array sums to 
  // 1 - sum(weights[0]..weights[i])
  // so rescale r appropriately.
  r -= weights[i];
}

даст вам желаемое распределение.

Хитрость r -=, которая гарантирует, чтоr всегда между 0 и суммой необработанных элементов массива.

Вы можете проверить это в http://jsfiddle.net/KdKdb/