Every year we do a raffle at my job with prizes that were donated by local businesses. Everyone can select 5 prizes they'd like to win from a total of x number of prizes. After that a winner is randomly selected for each prize and then the people who didn't win what they wanted will get a consolation prize from the pool of prizes nobody won.
I'm doing this all via PHP. I create an array that looks something like this:
$prizeArray[prizeID][$employeesWhoWantThisprizeArray[employeeIDs]]]
So for each key prize in the array, the value is an array of employees who want the prize. This can be anywhere from 0 to n employees. Then I just foreach through each prize, randomize the inner employee array, and pick a winner. The winner is added to an array of winners to be checked against so they only win one thing.
I should also point out that before going through each prize, I check to see if there are any prizes with only one employee attached. If there are, I automatically make that employee win that prize.
In the past, I just re-ran this script until I got the smallest number of losers I could. But I was wondering if there was a more efficient way than brute force to find this minimum loser count. Is there an existing mathematical equation or function that solves this kind of problem? I don't know much about math, so I'm not sure how to even google it. I'm not even sure what to tag this post with. Probability? Statistics, maybe? Arrays are kinda matrix-like, so I guess I'll throw that in there too.
Thanks!
If you want to find out the maximum possible number of winners, this is a maximum matching problem in a bipartite graph. The left nodes are people, the right nodes are prizes, and there is an edge between person and prize if that person selected that prize.