The Fisher-Yates shuffle (also called Knuth shuffle) gives you a fair shuffle in time.
Here's the idea: for position from to , pick a random index where , then swap elements at positions and . This ensures each element has equal probability of ending up in any position.
Why does this work? At step , you're choosing from the remaining elements with equal probability. The product of these choices gives each permutation probability .