Given integers M and N with M < N, your program should produce a sorted list of M random integers in the range 1...N, without duplicates. For instance, if M= 3 and N= 8, the output might be 2 3 5; and if M= 2 and N= 4, each of the six outputs 1 2, 1 3, 1 4, 2 3, 2 4, and 3 4 should be equally likely to appear. Your program should produce each M-element subset of 1...N equiprobably if you have a truly ``random'' random number generator. Instead, use a system function like rand or use your own custom-made generator.
Your program should be simple, elegant, clear, and efficient. It should work for M and N in as broad a range as possible. A simple algorithm generates a sequence of random integers in 1...N and tosses out duplicates---if you don't do this, be confident that your method produces random subsets as required. As usual, you must justify your choice of algorithm and data structure. Most likely, you will want to try more than one approach: start by doing something straightforward that you know you can get working quickly (but not so straightforward that its running time is quadratic!), then look for faster solutions. Document your algorithm design decisions.
Turn in the source code and runs for a sufficiently broad range of M and N to exhibit the best properties of your programs (particularly, correctness and efficiency). Show the CPU time and the number of duplicates generated for each run.
As usual, your goal is to find a decent method, not squeeze time out of a bad algorithm. For example, it should take a few seconds (not a few minutes) to generate 100,000 sorted distinct six digit integers.
Hints. Try a program with a main loop that reads an M, N pair and then writes the list of M integers. Check the random numbers that you generate before going any further: if they're bad, they may make a good algorithm look bad. Also, don't let the time taken for random number generation unduly influence your design decisions: you may want to get an idea of what that cost is by just seeing how long it takes to generate M (not necessarily distinct) integers.
Due: 11:59PM Thursday, March 2.