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:

1. Leads to unbiased permutations
2. Does not require the shuffling and storing of all duplicate elements

CodePudding user response：

Since a Fisher-Yates shuffle produces a random permutation, its inverse is also a random permutation:

1. For i=1 to n-1:
   1. choose a random number j in [0,i]
   2. swap elements i and j

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.