The Fisher–Yates algorithm generates unbiased random permutations of a finite sequence. The running time is proportional to the number elements being shuffled.
I want to shuffle a few non-zero elements with a large number of zero elements.
Implementing the Fisher–Yates algorithm with a list would lead to the shuffling process taking too long and requiring too much storage. Most steps in the Fisher--Yates algorithm would simply switch the position of duplicate zero elements.
Does there exists a random shuffle (or alternative) algorithm that:
Since a Fisher-Yates shuffle produces a random permutation, its inverse is also a random permutation:
In this algorithm, though, if you have m non-zero elements, and you start with all of them at the end, then the first n-m iterations are guaranteed to be swapping zeros, so you can just skip those.
Use a hash map instead of an array if you want to avoid storing all the zero elements.