Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

migrated from stackoverflow.com Feb 27 '12 at 20:41

This question came from our site for professional and enthusiast programmers.

    
is this homework? –  Gabriel Belingueres Feb 27 '12 at 16:39
    
Do you just want to pick a random subset of some fixed size from a big pool of candidates? Eg, you have 10 numbers (== players), and you want to pick 3 (== winners) of them? –  rrenaud Feb 27 '12 at 16:41
    
rrenaud --> OK I got it! Definitely no. Players will play this game and for each, I have to tell if he won or not. And eventually, I must have the exact number of winners by the time I reach the max number of players. –  Radada Feb 27 '12 at 16:56
1  
I still don't have any idea what you're trying to do.. "by the time I reach 500 players" "played this game".. what's this game? what makes somebody a winner? are they playing against each other? everyting you wrote is very confusing... please give sample input and output for your app –  Karoly Horvath Feb 27 '12 at 16:56
    
I think this is a streaming sampling problem. He sees players one at a time, and he needs to decide if a given player will be a winner or not at that instant, and he needs to guarantee that at the end of the sampling process, he has generated enough winners. –  rrenaud Feb 27 '12 at 16:59
show 6 more comments

2 Answers 2

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.

share|improve this answer
    
Thank you @amit but the list of users is not populated from scratch. It's a game 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, 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. –  Khal Feb 27 '12 at 20:51
    
@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 ith 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 winners –  amit Feb 28 '12 at 0:23
add comment

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.

share|improve this answer
    
thx for your help @rrenaud, really appreciate it, especially regarding the "history" of this topic :D –  Khal Feb 29 '12 at 10:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.