How to shuffle an array so that all elements change their place

Question

I need to shuffle an array so that all array elements should change their location. Given an array [0,1,2,3] it would be ok to get [1,0,3,2] or [3,2,0,1] but not [3,1,2,0] (because 2 left unchanged). I suppose algorithm would not be language-specific, but just in case, I need it in C++ program (and I cannot use std::random_shuffle due to the additional requirement).

Answer 1

What about this?

1. Allocate an array which contains numbers from 0 to arrayLength-1
2. Shuffle the array
3. If there is no element in array whose index equals its value, continue to step 4; otherwise repeat from step 2.
4. Use shuffled array values as indexes for your array.

Answer 2

For each element e
    If there is an element to the left of e
        Select a random element r to the left of e
           swap r and e

This guarantees that each value isn't in the position that it started, but doesn't guarantee that each value changes if there's duplicates.

BeeOnRope notes that though simple, this is flawed. Given the list [0,1,2,3], this algorithm cannot produce the output [1,0,3,2].