Well, my sketch works, no?
What I did there: instead of filling the array with increasing indexes, then randomizing it by swapping values, I just combined the two operations: I take a random value amongst the previously computed ones, and I put it at the current index, then I put the value that should have been found at this place at the location that is just freed.