# How to create an algorithm for a raffle, where each raffle guarantees a winning ticket?

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.

• Is this homework? – Steven Burnap May 5 '16 at 23:10
• No, not at all... We are revisiting our current approach which did not work so well, and hope the community has a few pointers for us. . . – jottr May 5 '16 at 23:14
• You have to generate the pool of raffle ticket numbers in advance, prior to the drawing, and then randomly pick from that pool of numbers at drawing time. Am I missing something? – Robert Harvey May 5 '16 at 23:18
• What difference would it make if this would be homework though. The only person at a loss would be the one not doing her homework... – jottr May 5 '16 at 23:19
• Are you talking about Powerball, where they draw the numbers one at a time? That game often results in there not being a winner. – Robert Harvey May 5 '16 at 23:48

If I understand what you are want, then:

``````create empty list
for 1..N:
do
r = random number
while r in 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
``````
• This would be the approach I'd take. I'd also consider whether having random ticket numbers is truly required or if sequential numbers as in a real-world raffle would suffice if you distributed tickets by, for each ticket, picking a random recipient and removing that recipient from the list. – Todd Knarr May 6 '16 at 0:27
• If you do this, use SecureRandom or whatever really good random number generator you have available. When I ran Windows, the media player shuffle was so bad it would play 5% of the songs 10 times while almost 40% of the songs were still unplayed. Also, you might want to shuffle the entries with one algorithm before picking them with another. Modern Linux has had a lot of thought put into /dev/random. Hashing the value in there might not be great by every measure, but it's a good start. – GlenPeterson May 6 '16 at 19:27

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.

You can't.

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.