Mélanger un tableau sans biais (Fisher-Yates)

Algorithms & Data Structuresshufflerandomfisher-yatesarraysampling

Every language

12 langages, copy-ready. One at a time with syntax highlighting, or all inline.

JSJavaScript

function shuffle(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1)); // 0..i, the remaining prefix
    [arr[i], arr[j]] = [arr[j], arr[i]];          // destructuring swap, no temp
  }
  return arr;
}

Math.floor, never Math.ceil — Math.random() is [0, 1), so ceil can produce arr.length and read past the end. The destructuring swap [a, b] = [b, a] is the idiomatic no-temp swap.

TSTypeScript

function shuffleInPlace<T>(arr: T[], rand: () => number = Math.random): T[] {
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(rand() * (i + 1)); // 0..i — never the full length
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

The injected rng is what makes this assertable: tests pass a seeded LCG and compare permutations exactly, production passes the Math.random default. Generic <T> keeps the caller's element type.

GoGo

import "math/rand/v2"

func shuffleInPlace[T any](arr []T) {
	rand.Shuffle(len(arr), func(i, j int) {
		arr[i], arr[j] = arr[j], arr[i]
	})
}

rand.Shuffle IS Fisher-Yates — the swap callback receives each pair it drew, so the in-place swap is all you write. math/rand/v2 is the modern API; on v1, rand.New(rand.NewSource(seed)) gives the seeded, reproducible generator.

RsRust

use rand::rngs::StdRng;
use rand::seq::SliceRandom;
use rand::SeedableRng;

let mut rng = StdRng::seed_from_u64(42); // seeded, reproducible
let mut arr = vec![1, 2, 3, 4, 5];
arr.shuffle(&mut rng); // Fisher-Yates internally

// hand-rolled when the rand crate is banned:
for i in (1..arr.len()).rev() {
    let j = rng.random_range(..=i); // 0..=i, the remaining prefix
    arr.swap(i, j);
}

SliceRandom::shuffle is Fisher-Yates internally — reach for it unless the crate is banned. The hand-roll walks (1..len).rev() and rng.random_range(..=i) is the inclusive bounded draw that keeps the prefix rule.

PHPPHP

function fisherYates(array $arr): array
{
    for ($i = count($arr) - 1; $i > 0; $i--) {
        $j = random_int(0, $i); // CSPRNG, 0..i — the remaining prefix
        [$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
    }
    return $arr;
}

The honest stdlib gap: shuffle($arr) exists but is not seedable reproducibly the way tests need, and it resets keys — a shuffle of [a => 1] comes back [0 => 1]. random_int is the CSPRNG draw; for determinism tests seed with mt_srand($seed) and draw mt_rand(0, $i).

PyPython

import random

random.shuffle(items)          # in-place, returns None — a common trap
shuffled = random.sample(items, len(items))  # non-mutating copy

rng = random.Random(42)       # seeded instance, reproducible
rng.shuffle(items)

random.sample(items, k) is the non-mutating spelling — it returns a new list, so len(items) gives the full shuffled copy. random.shuffle returns None, never assign from it. secrets has no shuffle: for cryptographic draws, sample indices with secrets.randbelow(i + 1) and swap yourself.

C#C#

static void Shuffle<T>(T[] arr)
{
    for (int i = arr.Length - 1; i > 0; i--)
    {
        int j = Random.Shared.Next(i + 1);   // 0..i — the remaining prefix
        (arr[i], arr[j]) = (arr[j], arr[i]); // tuple swap
    }

    // raffle-grade draws:
    // int j = System.Security.Cryptography.RandomNumberGenerator.GetInt32(i + 1);
}

The gap: no stdlib shuffle — hand-roll it. The classic WRONG version is the forward loop with Next(arr.Length) each pass: a fresh full-range draw makes some permutations reachable by more swap paths than others, so small decks visibly clump. Next(i + 1) draws from the remaining prefix only; RandomNumberGenerator.GetInt32 is the CSPRNG version.

JvJava

import java.util.Collections;
import java.util.List;
import java.util.Random;

Collections.shuffle(list);                  // Fisher-Yates via pairwise List.set
Collections.shuffle(list, new Random(42)); // seeded, reproducible

// shared Random across threads is the parallel trap:
Collections.shuffle(list, java.util.concurrent.ThreadLocalRandom.current());

Collections.shuffle IS Fisher-Yates, swapping pairwise through List.set. For parallel work use ThreadLocalRandom — a single shared Random under concurrent calls contends and can return duplicated draws.

SwSwift

var array = [1, 2, 3, 4, 5]
array.shuffle()   // in-place; RandomNumberGenerator defaults to .systemRandom
let shuffled = array.shuffled()  // copy

// hand-rolled, e.g. with a seeded generator passed to shuffle(using:):
for i in stride(from: array.count - 1, through: 1, by: -1) {
    let j = Int.random(in: 0...i)   // 0...i, the remaining prefix
    array.swapAt(i, j)
}

stride(from: count-1, through: 1, by: -1) is the inclusive backwards walk — through: 1 stops before the last no-op swap at 0. shuffle(using:) takes any RandomNumberGenerator, including a seeded one you control.

KtKotlin

val shuffled = list.shuffled()               // new list
list.shuffle()                               // in-place on a MutableList

list.shuffle(java.util.Random(42))          // seeded via the JVM Random
list.shuffle(kotlin.random.Random(42))      // Kotlin's own seedable Random

kotlin.random.Random is the default generator — kotlin.random.Random(seed) is its seedable variant, java.util.Random(seed) drops in for JVM interop. shuffled() on a List is the copy spelling; shuffle() needs a MutableList.

RbRuby

shuffled = items.shuffle                     # copy
items.shuffle!                              # in-place, returns self

rng = Random.new(42)
items.shuffle!(random: rng)                 # seeded, reproducible

# the hand-roll, for teaching:
i = items.length
while i > 1
  i -= 1
  j = rng.rand(i + 1)                       # 0..i, the remaining prefix
  items[i], items[j] = items[j], items[i]
end

shuffle!/shuffle accept random: Random.new(seed) — the seeded generator that makes assertions exact. The hand-roll is the same multiple-assignment swap every other language spells with a temp.

ZigZig

const std = @import("std");

fn shuffleInPlace(comptime T: type, arr: []T, prng: *std.Random.DefaultCsprng) void {
    const random = prng.random();
    var i: usize = arr.len;
    while (i > 1) {
        i -= 1;
        const j = random.uintLessThan(usize, i + 1); // 0..i, unbiased
        std.mem.swap(T, &arr[i], &arr[j]);
    }
}

// OS CSPRNG, no state to thread: std.crypto.random.uintLessThan(usize, i + 1)

uintLessThan(usize, i + 1) is the bounded draw done right — a raw uint modulo a non-power-of-two bound would bias the tail. std.crypto.random is the OS-CSPRNG variant for raffle-grade draws; DefaultCsprng.init(seed) gives the seeded, reproducible generator.

Mélanger un tableau sans biais (Fisher-Yates) snippet

Every language