Fisher–Yates Shuffle (All Permutations Equally Likely)

"""
Given an array of n elements, randomly shuffle the array such that every possible permutation has equal probability of occurring.

The shuffle must be done efficiently in-place using O(1) extra space and O(n) time.

Shuffles the array in-place using the Fisher–Yates algorithm (forward version).At each step, we pick a random element only from the part of the array that has not been shuffled yet and place it at the current position.

A common doubt is: “Later positions have fewer choices, so is it unfair?” -> It is actually fair because when initial numbers got swapped, it might have also gone to later part which make each numbers probability to be on any position is same.
"""

import random
def shuffle_forward(arr):
    n = len(arr)

    for i in range(n):
        j = random.randint(i, n-1)  # pick from i to n-1
        arr[i], arr[j] = arr[j], arr[i]

    return arr