Shuffle an Array

Question:
Given an input array, shuffle it and output a randomized sequence.

Analysis:
The array can actually be of any type, not necessary integer or number. One special example is to shuffle a deck of cards. That happens to be of integer type.

Variations:
There may be different variations of this similar problem. I hope to summarize all the cases here and would like to go through each with some implementation.

1. Randomize an array of n elements
2. Randomly select m elements out of an array of n elements
3. Randomly select m elements out of a stream of n elements (n is known before hand)
4. Randomly select m elements out of a stream of elements (not sure how many elements there are until stopping reading)

This blog talks about Case 1. The code is not hard but there are some tricks. It's better to select from the end of array and that will help control the number of elements remained. Also, the code will be cleaner.


The mathematical proof would be trickier and it's good to have some combinatorics. The probability of any output sequence will be \[\frac{1}{n!}\]