Fisher–Yates Shuffle

Definition

Definition

The Fisher-Yates Shuffle Algorithm, also known as the Knuth Shuffle, is a method for generating a random permutation of a finite sequence. It efficiently shuffles elements within an array or list, ensuring each permutation has an equal probability of occurrence

Explanation

Start by having an array containing the elements to be shuffled. Proceed by traversing the array, moving from the last element to the second. During each iteration, generate a random index within the inclusive range of 0 to the current index. Subsequently, swap the element located at the current index with the element positioned at the randomly chosen index. Repeat this process until all elements within the array have undergone shuffling. This algorithm ensures that each element within the array has an equal probability of appearing at any position, resulting in a random permutation of the original sequence

Guidance

• Begin with an array of elements to be shuffled
• Start iterating backward through the array, from the last element to the second
• At each iteration
  • Generate a random index randomIndex between 0 and the current index (inclusive)
  • Swap the element at the current index with the element at randomIndex
• Continue this process until all elements have been shuffled

Tips

• ensure that your random number generator is capable of producing uniformly distributed random numbers
• avoid using inefficient random number generators to maintain the algorithm's time complexity
• double-check your implementation to ensure that each element has an equal probability of ending up in any position within the array

Practice

Practice

fisherYatesShuffle(array):
  n = length(array)
  for i from n-1 down to 1:
    randomIndex = random(0, i)
    swap(array[i], array[randomIndex])

Solution

package main

import (
	"math/rand"
)

func shuffle(arr []int) {
	for i := len(arr) - 1; i > 0; i-- {
		j := rand.Intn(i + 1)
		arr[i], arr[j] = arr[j], arr[i]
	}
}

import java.util.Arrays;
import java.util.Random;

public class FisherYatesShuffle {

  public static void shuffle(int[] arr) {
    Random rand = new Random();
    for (int i = arr.length - 1; i > 0; i--) {
      int j = rand.nextInt(i + 1);
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }
}

function shuffle(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
}

import java.util.*

fun shuffle(arr: IntArray) {
    val rand = Random()
    for (i in arr.size - 1 downTo 1) {
        val j = rand.nextInt(i + 1)
        val temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
    }
}

import random

def shuffle(arr):
    for i in range(len(arr) - 1, 0, -1):
        j = random.randint(0, i)
        arr[i], arr[j] = arr[j], arr[i]

use rand::seq::SliceRandom;
use rand::thread_rng;

fn shuffle(arr: &mut [i32]) {
    let mut rng = thread_rng();
    arr.shuffle(&mut rng);
}

function shuffle(arr: number[]) {
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
}