I am looking for an algorithm to create a raffle, where each participant is assigned a ticket with a random series of numbers.
Each raffle hast N participants, and there should exist same amount of raffle tickets, one ticket per user.
The user should know her ticket numbers before the draw, so she can follow the draw, and anticipate if she is a winner.
Each raffle has a minimum of one winner.
Some raffles can have two or more winning tickets, whereas each ticket can only win once. A winning ticket is removed from the current raffle.
If there is more than one winning ticket available, this should be determined before the beginning of the raffle.
It should be impossible to draw blanks.
How could a raffle with such properties be created. Or more specifically:
How can we generate the raffle numbers, and tickets as such, that each raffle has one or (1+N) guaranteed winning ticket.
How can we avoid blanks?
Pseudocode would be great, and/or a few pointers of maybe well known algorithms solving similar issues.
If I understand what you are want, then:
create empty list for 1..N: do r = random number while r in list add r to list give ticket with r to person for number of winners: r = random element in list announce r as a winner remove r from list
It seems that the hard part of your problem is stated in your comment where you say you want to choose the winning number by ‘drawing’ random single digits and combing them
To guarentee a winner you have to pick a winning ticket from a list of sold tickets. Normally you would simply record a list of tickets sold and pick.one of them randomly to get the winner.
You could then annouce the winning digits one at a time?
If you want to randomly draw the digits though, you are going to have to restrict the possible results. Ie. If you have only sold 1200 tickets, you can only pick 4 numbers and the first one can only be 1 or 0 and so on.
You might find then that the resulting winning number or numbers is no longer random. Ie. If you can win by matching 3 numbers, 1 and 0 are good ones to pick.
In fact thinking about it this also applies if you select the whole number from the list of winners and allow players to select their numbers.
Having a series of numbers on a ticket (eg. 3 7 11 13 14 25) randomly given to N participants where N is a very low number (eg. 23) and then devising an algorithm where you can draw one number at a time making sure that you will pick a winner (most likely having a few participants still believing they could be a winner quite far into the drawing) just doesn’t add up.
Of course you could give the 23 participants the ticket 1, 2, 3, 4, 5, 5+n where n is the number of the participant. Then draw the numbers 1, 2, 3, 4, 5 and then draw 5+x where x is between 1 and the number of participants. But I doubt that people will find it entertaining in week two.