1
$\begingroup$

I have some sort of a math issue : I have to implement an algorithm that randomly generates winners and losers based on :

  • a maximum number of players
  • a percentage of winners to reach

Of course, the more winners, the smaller the effective percentage will be, but in the end, when the total number of players reach the maximum number that was set, the exact percentage of winners must be reached too.

In other words, if I set the maximum number of players to 500 and the percentage to 10%, I have to reach exactly 50 winners (no less, no more) by the time I reach 500 players. I tried to do some math, but I'm not really good at it, so I'm looking for your help ;)

EDIT : here's another try to explain my problem since it seems that I'm confusing people :D :D

It's a game on iPad where people come and play. An admin first sets the maximum number of users and the percentage of winners he'd like.

Then, people come and play, one at a time, and when they do, they are notified instantly if they won or not. By the time the game reaches the maximum number of players that was initially set, I must have the correct percentage of winners based on what was initially set. I hope this description is more clear ;)

Thanks a lot for your help.

  • 0
    @Khal: the question has since then been merged into your account. Now you should be able to comment on this question and/or mark an answer as accepted.2012-05-24

2 Answers 2

4

Easiest way to do it [in my opinion], if you need k% winners, out of n players, is populating a list and shuffling using fisher-yates shuffle, and then pick the first k%:

1. populate a list of size n containing: [1,2,...,n] 2. shuffle the list 3. take the a sublist containing the first k% of elements -    it is the indexes of the winners out of all players 

(*) p.s. I am not familiar with objective-c, but I can only assume an implementation for fisher-yates already exist in it.

  • 0
    @Khal: No need for prepopulated list. When first player comes, you create a list of size `n`, and shuffle it, and get your first `k%` elements. This is actually a sublist of `[1,...,500]`. Assume this list contains an element `i`. When the `i`th player enters the game, he wins. Note that you did not need to know who this player is beforehand - your list only knows the **index** of the winners2012-02-28
0

You start and you are given N, the maximum number of players, and p, the percentage of winners. From that, you know the total number of winners is k=p*N. Now you just need to keep an incremental count of k and N as the game progresses. You get a new player, generate a uniform random number between 0 and 1, if it's less than k/N, he won, and k and N are decremented. Otherwise, he lost and only N is decremented, and the chance the next player wins goes up.

This works and there is no apriori bias as to who will win based on what position a player joins. That k/N winning probability is changing as the game goes on, but that is necessary to meet your requirement that the original p percent of people win.

  • 0
    thx for your help @rrenaud, really appreciate it, especially regarding the "history" of this topic :D2012-02-29