Fisher–Yates Shuffle

Generating a random permutation of a finite sequence.

O(n^2)

The basic method given for generating a random permutation of the numbers 1 through N goes as follows:

1. Write down the numbers from 1 through N.
2. Pick a random number k between one and the number of unstruck numbers remaining (inclusive).
3. Counting from the low end, strike out the kth number not yet struck out, and write it down at the end of a separate list.
4. Repeat from step 2 until all the numbers have been struck out.
5. The sequence of numbers written down in step 3 is now a random permutation of the original numbers.

It is obvious that at each step, a number has equal possibility to be picked out.

Or we can consider it in the other way: at each step the number we will pick will have sizeof(remaining_list) possibilities. So overall we will have n! possibilities.

O(n)

-- To shuffle an array a of n elements (indices 0..n-1):
for i from 0 to n−2 do
     j ← random integer such that i ≤ j < n
     exchange a[i] and a[j]

vector<int> shuffle(vector<int> const& origin) {
  vector<int> res = origin;
  for (int i = 0; i + 1 < res.size(); ++i) {
    int j = i + rand() % (res.size() - i);
    swap(res[i], res[j]);
  }
  return res;
}

The correctness is also obvious. We basically use the original array as the separate list.