Làm Chủ Tạo Số Ngẫu Nhiên Có Trọng Số: Kỹ Thuật & Ứng Dụng

Số ngẫu nhiên thường theo "phân phối đều" (uniform distribution), nghĩa là mọi số có xác suất được chọn như nhau.

Nhưng nếu muốn một số số được chọn thường xuyên hơn, cần chiến lược khác: bộ sinh số ngẫu nhiên có trọng số (weighted random number generator).

Một số ứng dụng thực tế:

• Bảng战利品 (loot table) trong game video, kẻ thù rơi vật phẩm khác nhau với tỷ lệ rơi khác nhau.
• Xổ số (raffle), người có nhiều vé hơn có cơ hội trúng cao hơn.

Chiến Lược Đơn Giản

Nghĩ về ví dụ xổ số, giải pháp rõ ràng: tạo mảng chứa một bản sao của vật phẩm cho mỗi "vé".

Ví dụ, John mua 4 vé, David chỉ 1, John sẽ có 4 lần cơ hội trúng hơn David.

Triển khai hoạt động:

users = { john: 4, david: 1 }
raffle = []
users.map do |name, tickets|
  tickets.times { raffle << name }
end
p raffle # [:john, :john, :john, :john, :david]
p raffle.sample # :john

Thêm tên người một lần cho mỗi vé họ mua, rồi chọn ngẫu nhiên tên từ danh sách. Do xuất hiện nhiều lần hơn, tăng cơ hội tên đó được chọn.

Thích cách này vì đơn giản và khi đã có danh sách, chọn người thắng rất nhanh.

Tổng Trọng Số

Có cách khác hiệu quả hơn về bộ nhớ, đánh đổi là chọn giá trị ngẫu nhiên chậm hơn.

Ý tưởng: chọn số ngẫu nhiên giữa 1 và tổng tất cả trọng số, sau đó lặp cho đến khi tìm thấy trọng số nhỏ hơn hoặc bằng số này.

Code:

def random_weighted(weighted)
  max = sum_of_weights(weighted)
  target = rand(1..max)
  weighted.each do |item, weight|
    return item if target <= weight
    target -= weight
  end
end

def sum_of_weights(weighted)
  weighted.inject(0) { |sum, (item, weight)| sum + weight }
end

Code nhận hash với key là vật phẩm, value là trọng số. Gọi phương thức như sau:

random_weighted(cats: 5, dogs: 1) # :cats

Kiểm tra hoạt động đúng bằng cách xem phân phối kết quả sau nhiều lần chạy.

Ví dụ:

counts = Hash.new(0)
def pick_number
  random_weighted(cats: 2, dogs: 1)
end
1000.times { counts[pick_number] += 1 }
p counts

Chạy vài lần và xem đầu ra để biết tỷ lệ có đúng không.

Kết Luận

Mặc dù có thuật toán phức tạp hơn, hai cách này đã đủ tốt. Hy vọng bài viết hữu ích, hãy chia sẻ với bạn bè để mình tiếp tục viết thêm!