algorithmrandompermutationshufflefisher-yates-shuffle

Unbiased Shuffling with Large Number of Duplicates


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

Solution

  • 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.