CODEWITHSUNDEEP
rubyrandomweighted
Trip
Trip

Reputation: 27114

In Ruby, how can one make a weighted random selection by least weight?

If I have the array :

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

I could reduce this to the amount of occurrences :

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

Now I would like to choose at random with the least used number in ar being more weighted

I understand how I could easily make a weighted random choice based on most commonly used number, but not its inverse.

Upvotes: 5

Views: 2838

Answers (2)

engineersmnky
engineersmnky

Reputation: 29478

It seems like this would work for you: 

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

We group the elements and count them then we create a new Array with the number of elements inverted to favor the lesser occurrences. e.g. 

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}

Since 5 occurred once originally it now occurs 14 times (same with 4 and 7). So 5,4, and 7 have equal likelihood of being chosen and are each twice as likely as 1 and 3 which occured twice and 7 times as likely as 6.

Also maybe something like this might be more efficient

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

Upvotes: 3

iGian
iGian

Reputation: 11193

If you already have an algorithm for making a random weighted choice, one option to swap the weight can be as follows.

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}

That's the idea.

Can be refactored to be more Rubyish:

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}

Upvotes: 1

Related Questions