Случайным образом перемешать взвешенный массив

Вот, скорее всего, неэффективное, но, надеюсь, достаточно эффективное решение: (Хотя я не обещаю правильности! К тому же этот код не сделает слишком многих рубистов счастливыми...).

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

def shuffle some_hash
   result = []

   numbers = some_hash.keys
   weights = some_hash.values
   total_weight = weights.reduce(:+)

   # choose numbers one by one
   until numbers.empty?
      # weight from total range of weights
      selection = rand() * total_weight

      # find which element this corresponds with
      i = 0
      while selection > 0
         selection -= weights[i]
         i += 1
      end
      i -= 1

      # add number to result and remove corresponding weight
      result << numbers[i]
      numbers.delete_at i
      total_weight -= weights.delete_at(i)
   end

   result
end

Вот еще один способ выполнения взвешенной случайной выборки с использованием Enumerable#max_by и этот удивительный результат от Эфраимидиса и Спиракиса:

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

# hash of ids with their respective weights that sum to 1
y = { 1 => 0.7, 2 => 0.2, 3 => 0.1 }

# lambda that randomly returns a key from y in proportion to its weight
wrs = -> { y.max_by { |_, weight| rand ** (1.0/weight) }.first }

# test run to see if it works
10_000.times.each_with_object(Hash.new(0)) { |_, freq| freq[wrs.call] += 1 }

# => {1=>6963, 3=>979, 2=>2058}

Кстати, были разговоры о добавлении взвешенной случайной выборки в Array#sample, но эта функция, кажется, затерялась в случайном порядке.

Дальнейшее чтение:

1. Ruby-Doc для Enumerable#max_by — особенно wsample пример
2. взвешенная случайная выборка Эфраимидиса и Спиракиса (2005 г.), которая представляет алгоритм
3. Новые функции для Array#sample, Array#choice, в которых упоминается намерение добавление взвешенной случайной выборки к Array#sample

Вы дали функцию плотности вероятности (P для «вероятности»):

P(1) = 0.7
P(2) = 0.3
P(3) = 0.1

Вам нужно построить (кумулятивную) функцию распределения, которая выглядит так:

Теперь мы можем сгенерировать случайные числа от нуля до единицы, нанести их на ось Y, провести линию вправо, чтобы увидеть, где они пересекаются с функцией распределения, а затем считать связанную координату X как случайную переменную. Таким образом, если случайное число меньше 0,7, случайная величина равна 1; если находится в диапазоне от 0,7 до 0,9, случайная величина равна 2, а случайная величина равна 3, если вероятность превышает 0.9. (Обратите внимание, что вероятность того, что rand будет точно равна 0.7 (скажем) точно, практически равна нулю, поэтому нам не нужно сожалеть о различиях между < 0.7 и <= 0.7.)

Чтобы реализовать это, сначала вычислите хэш df:

y = { 1 => 0.7, 2 => 0.2, 3 => 0.1 }

last = 0.0
df = y.each_with_object({}) { |(v,p),h| last += p; h[last.round(10)] = v }
  #=> {0.7=>1, 0.9=>2, 1.0=>3}

И теперь мы можем создать случайную переменную следующим образом:

def rv(df)
  rn = rand
  df.find { |p,_| rn < p }.last
end

Давай попробуем:

def count(df,n)
  n.times.each_with_object(Hash.new(0)) { |_,count|
    count[rv(df)] += 1 }
end

n = 10_000
count(df,n)
  #=> {1=>6993, 2=>1960, 3=>1047} 
count(df,n)
  #=> {1=>6986, 2=>2042, 3=>972} 
count(df,n)
  #=> {1=>6970, 2=>2039, 3=>991} 

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

Если вы сделаете свои веса целочисленными значениями, например:

y = { 1 => 7, 2 => 2, 3 => 1 }

Затем вы можете создать массив, в котором количество вхождений каждого элемента в массиве основано на весах:

weighted_occurrences = y.flat_map { |id, weight| Array.new(weight, id) }
# => [1, 1, 1, 1, 1, 1, 1, 2, 2, 3]

Тогда сделать взвешенное перемешивание так же просто, как:

weighted_occurrences.shuffle.uniq

После 10 000 перетасовок и выбора первых идентификаторов я получаю:

{
  1 => 6988,
  2 => 1934,
  3 => 1078
}