The Fisher–Yates Random Shuffle Algorithm

Given an array, we want to shuffle it (to make it random), so that every possible random solution gets evenly-distributely possibility. One may quickly write a solution like this, which seems correct, but it is not:

1
2
3
4
5

void shuffleArray(vector<int> &array) {
  for (int i = 0; i < array.size(); ++ i) {
    swap(array[i], (rand % array.size()));
  }
}

void shuffleArray(vector<int> &array) {
  for (int i = 0; i < array.size(); ++ i) {
    swap(array[i], (rand % array.size()));
  }
}

Why? because some elements may be swapped more than once. For example:

[1, 2, 3] // lets swap 1 and 2
[2, 1, 3] // lets swap 1 and 3
[2, 3, 1]

For each solution to be fairly picked, we need to rule out the elements that have been swapped out. Considering two baskets, each time, you randomly pick some egg (number) from that basket and put it in order into another one. The numbers that are put to another could not be chosen again. This is the idea of the Fisher-Yates Random shuffle algorithm.

C++ Random Shuffle Algorithm

We can do this in-place by the following C++ implementation:

1
2
3
4
5
6

void shuffleArray(vector<int> &array) {
  for (int i = 0; i < array.size(); ++ i) {
    // random(a, b) returns a random number between a (inclusive) and b (exclusive)
    swap(array[i], random(i, array.size());
  }
}

void shuffleArray(vector<int> &array) {
  for (int i = 0; i < array.size(); ++ i) {
    // random(a, b) returns a random number between a (inclusive) and b (exclusive)
    swap(array[i], random(i, array.size());
  }
}

We get a random index between the current index i to the size of the list, thus separating the list into two parts: the basket chosen and the basket to choose from. The time complexity for Fisher-Yates Random Shuffle algorithm is O(N) and space complexity is O(1) constant where the swapping takes inplace.

Random Shuffling in Magik

With SW521, the Random object has been re-implemented using Java Interop Library (make use of the java.util.Random object), the random.between() method generates a random integer between two bounds (inclusive). The following is the Random Shuffle extended API to the Magik programming language.

_package sw
$

_pragma(classify_level=public, topic=random)
_method random.shuffle(list)
    ## Shuffle an array using Fisher–Yates
    ## 
    _local i << 1, len << list.size
    _while i <= len
    _loop
        _local j << _self.between(i, len)
        (list[i], list[j]) << (list[j], list[i]) # swapping in Pythonic way.
        i +<< 1
    _endloop
    >> list
_endmethod

Random Shuffling Algorithms

• The Fisher–Yates Random Shuffle Algorithm
• GoLang: Shuffle the Array
• Teaching Kids Programming – The Fisher–Yates Random Shuffle Algorithm in Python

–EOF (The Ultimate Computing & Technology Blog) —