Random Integers, No Repeats

[Albert Chan]

(08-09-2023 03:50 PM)John Keith Wrote:  I would bet that rand uses the Fisher-Yates algorithm internally.

Yes. We need n-1 random numbers, O(n) is as good as we can get.

Conversely, for list x to y, shuffled, number of swaps to restore it is also O(n)
(assume we don't cheat, and just return new list x to y)

We can think of this kind of sort as inverse Fisher-Yates.

Example, Fifteen Puzzle Game Solvability in O(n).