# The Fisher-Yates Algorithm

·

### No headings in the article.

First, let's see how this algorithm work by using an example.

Say we have an array `[1, 2, 3, 4, 5]` and we want to shuffle it randomly.

For Fisher–Yates shuffle, we need to loop through the array. With every loop, we select an element randomly and swap it with the current index value.

We can see a process below.

``````array: [1,2,3,4,5], current index: 4, randomly choose an index from [0,4] => 0
swap index 4 and index 0, index -= 1;

array: [5,2,3,4,1], current index: 3, randomly choose an index from [0,3] => 1
swap index 3 and index 1, index -= 1;

array: [5,4,3,2,1], current index: 2, randomly choose an index from [0,2] => 2
swap index 2 and index 2, index -= 1; (note here, current index and selected index can be equal)

array: [5,4,3,2,1], current index: 1, randomly choose an index from [0,1] => 0
swap index 0 and index 1, index -= 1;

array: [4,5,3,2,1], current index: 0
Now current index is 0, no need to swap, return
``````

Now let's use it to solve the leetcode Shuffle an Array problem.

``````class Solution {
private original: number[];
private nums: number[];

constructor(nums: number[]) {
this.nums = nums;
this.original = nums.slice();
}

reset(): number[] {
this.nums = this.original.slice();
return this.nums;
}

shuffle(): number[] {
for (let i = this.nums.length - 1; i > 0; i--) {
// choose a random index from [0, i]
const randomIdx = Math.trunc(Math.random() * (i + 1));
// swap
[this.nums[randomIdx], this.nums[i]] = [this.nums[i], this.nums[randomIdx]];
}

return this.nums;
}
}
``````