What good algorithms are there for shuffling (scrambling) 1 to n objects?

Question

I have seen many algorithms for generating random numbers, so I wondered what common algorithms exist for scrambling a set of given numbers (or objects).

The numbers or objects need not be in any particular order (e.g. $1,2,3, ..., n$).

There are several online shuffling programs and some are part of common programs such as Excel. So I am interested in:

1. well-known shuffling algorithms
2. how they compare to the expected number of fixed points (i.e. rencontres numbers, I believe)
3. any known issues with such algorithms
4. any known comparisons, e.g. Excel's number shuffler versus Python's

Answer 1

Fisher Yates is a proper (uniform) shuffle and efficient. Uniform in that all permutations are created equally.

It has been around since 1938 but a few poker sites got it wrong and it was exploited.

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

There are n! permutations and Fisher mimics that.

Issues are if random is not random. Don't create a new random with each shuffle and shuffle from the prior shuffle (not a clean deck). Unless they knew the initial seed they could not pick up a pattern (without a LOT of hands - like approaching infinity).

A common problem is actually too many permutations and some are produced more than others. For example, swap every element with every other element (no j ≤ i).

Another problem is not allow a card to stay in its current position. If ace spades came off first then it cannot come off first next time.