--- date: '2024-01-30' description: Fisher-Yates shuffle algorithm id: Fisher-Yates modified: 2026-06-05 15:08:05 GMT-04:00 tags: - seed title: Fisher-Yates created: '2024-01-30' published: '2024-01-30' pageLayout: default slug: thoughts/Fisher-Yates permalink: https://aarnphm.xyz/thoughts/Fisher-Yates.md generator: quartz: v4.6.0 hostedProvider: Cloudflare baseUrl: aarnphm.xyz full: https://aarnphm.xyz/llms-full.txt --- Produced an _unbiased_ permutation: every permutation is equally likely. Pseudocode:

"\\begin{algorithm}\n\\caption{Fisher-Yates shuffle}\n\\begin{algorithmic}\n\\REQUIRE An array $A$ of length $n$\n\\FOR{$i = n-1$ \\TO $1$}\n \\STATE $j \\gets$ random integer such that $0 \\leq j \\leq i$\n \\STATE swap $A[i]$ and $A[j]$\n\\ENDFOR\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 1 Fisher-Yates shuffle

Require: An array $A$ of length $n$

1:for $i = n-1$ to $1$ do

2: $j \gets$ random integer such that $0 \leq j \leq i$

3:swap $A[i]$ and $A[j]$

4:end for

Implementation of modern Fisher-Yates algorithm

In [ ]:

JavaScript cell

```js title="FisherYates.js" function sample(obj, n, guard) { if (n == null || guard) { if (!isArrayLike(obj)) obj = values(obj) return obj[random(obj.length - 1)] } var sample = toArray(obj) var length = getLength(sample) n = Math.max(Math.min(n, length), 0) var last = length - 1 for (var index = 0; index < n; index++) { var rand = random(index, last) var temp = sample[index] sample[index] = sample[rand] sample[rand] = temp } return sample.slice(0, n) } ```