python lottery suggestion

Question

I know python offers random module to do some simple lottery. Let say random.shuffle() is a good one.

However, I want to build my own simple one. What should I look into? Is there any specific mathematical philosophies behind lottery?

Let say, the simplest situation. 100 names and generate 20 names randomly.

I don't want to use shuffle, since I want to learn to build one myself.

I need some advise to start. Thanks.

Answer 1

See the Fisher-Yates Shuffle, described also in Knuth's The Art of Computer Programming.

Answer 2

You can use: random.sample

Return a k length list of unique elements chosen from the population sequence. Used for random sampling without replacement.

For a more low-level approach, use `random.choice', in a loop:

Return a random element from the non-empty sequence seq.

The pseudo-random generator (PRNG) in Python is pretty good. If you want to go even more low-level, you can implement your own. Start with reading this article. The mathematical name for lottery is "sampling without replacement". Google that for information - here's a good link.

Answer 3

The main shortcoming of software-based methods of generating lottery numbers is the fact that all random numbers generated by software are pseudo-random.

This may not be a problem for your simple application, but you did ask about a 'specific mathematical philosophy'. You will have noticed that all commercial lottery systems use physical methods: balls with numbers.

And behind the scenes, the numbers generated by physical lottery systems will be carefully scrutunised for indications of non-randomness and steps taken to eliminate it.

As I say, this may not be a consideration for your simple application, but the overriding requirement of a true lottery (the 'specific mathematical philosophy') should be mathematically demonstrable randomness

Answer 4

You can generate your own pseudo-random numbers -- there's a huge amount of theory behind that, start for example here -- and of course you won't be able to compete with Python's random "Mersenne twister" (explained halfway down the large wikipedia page I pointed you to), in either quality or speed, but for purposes of understanding, it's a good endeavor. Or, you can get physically-random numbers, for example from /dev/random or /dev/urandom on Linux machines (Windows machines have their own interfaces for that, too) -- one has more pushy physical randomness, the other one has better performance.

Once you do have (or borrow from random;-) a pseudo-random (or really random) number generator, picking 20 items at random from 100 is still an interesting problem. While shuffling is a more general approach, a more immediately understandable one might be, assuming your myrand(N) function returns a random or pseudorandom int between 0 included and N excluded:

def pickfromlist(howmany, thelist):
  result = []
  listcopy = list(thelist)
  while listcopy and len(result) < howmany:
    i = myrand(len(listcopy))
    result.append(listcopy.pop(i))
  return result

Definitely not maximally efficient, but, I hope, maximally clear!-) In words: as long as required and feasible, pick one random item out of the remaining ones (the auxiliary list listcopy gives us the "remaining ones" at any step, and gets modified by .pop without altering the input parameter thelist, since it's a shallow copy).

Answer 5

I praise your desire to do this on your own.

Back in the 1950's, random numbers were unavailable to most people without a supercomputer (of the time). The RAND corporation published a book called a million random digits with 100,000 normal deviates which had, literally, just that: random numbers. It was awesome because it enabled laypeople to use high-quality random numbers for research purposes.

Now, back to your question.

I recommend you read the instructions on how to use the book (yes, it comes with instructions) and try to implement that in your Python code. This will not be efficient or elegant, but you will understand the implications of the algorithm you ultimately settle for. I love the part that instructs you to

open the book to an unselected page of the digit table and blindly choose a five-digit number; this number with the first number reduced modulo 2 determines the starting line; the two digits to the right of the initially selected five-digit number are reduced modulo 50 to determine the starting column in the starting line

It was an art to read that table of numbers!

To be sure, I'm not encouraging you to reinvent the wheel for production code. I'm encouraging you to learn about the art of randomness by implementing a clever, if not very efficient, random number generator.

My work requires that I use high-quality random numbers, on limited occasions I have found the site www.random.org a very good source of both insight and material. From their website:

RANDOM.ORG offers true random numbers to anyone on the Internet. The randomness comes from atmospheric noise, which for many purposes is better than the pseudo-random number algorithms typically used in computer programs. People use RANDOM.ORG for holding drawings, lotteries and sweepstakes, to drive games and gambling sites, for scientific applications and for art and music.

Now, go and implement your own lottery.