CODEWITHSUNDEEP
arrayssortingactiverecordrandom
Tkendall
Tkendall

Reputation: 15

Random selection of weighted items

My model TicketBuyer columns include ticket_buyer name and number_of_tickets purchased. I want to randomly select a winning ticket. I think my preference is to create another model (SelectTable) that has the ticket_buyer name replicated over the number of rows equal to the number_of_tickets purchased, thereby giving equal weight to each record. I can then just run a simple sort and pick the first record in the new table. I am having trouble auto creating the table with the correct number of rows for each ticket_buyer. Of course, there may be a more eloquent/ efficient way to do this as well. Advice is much appreciated.

Upvotes: 1

Views: 42

Answers (1)

samgak
samgak

Reputation: 24427

If speed isn't a problem you can do it without creating any extra data structures.

  • Find the maximum number_of_tickets bought by anyone
  • Randomly select a ticket buyer
  • Do another draw, with a number_of_tickets / max_number_of_tickets chance of them becoming the winner
  • If they fail the second draw, randomly select another ticket buyer and repeat the process until someone wins

Unless there is some crazy distribution like one person buys a million tickets and everyone else buys one, this shouldn't take too long.

Pseudo-code:

 max_tickets = max(table:number_of_tickets)
 while true do:
     // select a random buyer
     buyer = select random row from table

     // assume random(n) returns an integer number from 0 to n - 1 inclusive:
     if random(max_tickets) < buyer.number_of_tickets then
          return buyer   // we have a winner
 end

Upvotes: 1

Related Questions