В Ruby, как можно сделать взвешенный случайный выбор по наименьшему весу? - PullRequest
Новая
       54

В Ruby, как можно сделать взвешенный случайный выбор по наименьшему весу?

3 голосов
/ 09 мая 2019

Если у меня есть массив:

ar = [1,3,5,3,6,1,4,6,7,6,6,6,6,6]

Я мог бы уменьшить это до количества вхождений:

counts = {1=>2, 3=>2, 5=>1, 6=>7, 4=>1, 7=>1}

Теперь я хотел бы выбрать в случайном порядке , где наименее используемое число в ar равно больше взвешено

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

Ответы [ 2 ]

3 голосов
/ 09 мая 2019

Похоже, это будет работать для вас: 

arr = [1,3,5,3,6,1,4,6,7,6,6,6,6,6]

arr.group_by(&:itself).transform_values{|v| arr.size / v.size}.flat_map do |k,v| 
 [k] * v
end.sample

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

arr.group_by(&:itself).transform_values{|v| arr.size / v.size}.flat_map do |k,v| 
 [k] * v
end.group_by(&:itself).transform_values(&:size)
#=> {1=>7, 3=>7, 5=>14, 6=>2, 4=>14, 7=>14}

Так как 5 произошло однажды, теперь это происходит 14 раз (то же самое с 4 и 7). Таким образом, 5, 4 и 7 имеют одинаковую вероятность быть выбранными и каждый в два раза чаще, чем 1 и 3, что произошло в два раза и в 7 раз чаще, чем 6.

Также может быть что-то подобное может быть более эффективным 

grouping =arr.group_by(&:itself).transform_values(&:size).
scale = grouping.values.uniq.reduce(&:lcm)

grouping.flat_map do |k, v|
  [k]  * (scale / v)
end.sample
1 голос
/ 09 мая 2019

Если у вас уже есть алгоритм для случайного взвешенного выбора, один из вариантов обмена весом может быть следующим: 

grouping = ar.group_by { |n| n }.transform_values(&:size)
#=> {1=>2, 3=>2, 5=>1, 6=>7, 4=>1, 7=>1}
weights = grouping.values.uniq.sort
#=> [1, 2, 7]
reverse_mapping = weights.zip(weights.reverse).to_h
#=> {1=>7, 2=>2, 7=>1}
grouping.transform_values{ |v| reverse_mapping[v] }
#=> {1=>2, 3=>2, 5=>7, 6=>1, 4=>7, 7=>7}

Это идея.

Может быть изменен на более рубиновый: 
res = ar.group_by { |n| n }.transform_values(&:size).then do |h|
  rev_map = h.values.uniq.sort.then { |w| w.zip(w.reverse).to_h }
  h.transform_values{ |v| rev_map[v] }
end

#=> {1=>2, 3=>2, 5=>7, 6=>1, 4=>7, 7=>7}
...