55. Identical Probability Array Shuffling

Question: Write a function that shuffles an integer array with identical probability for all numbers.

Hints:

- This can be done linearly, splitting the array into two parts, shuffled one and not shuffled one,

- Start from 1st index and replace the current number with a random one from the array’s right part,

- Continue until you reach the end (all elements are shuffled).

Solution:

public func shuffle(array: inout [Int]) {
    // 1.
    let count = array.count
    for index in 0..<count {
        // 2.
        let destination = getRandom(floor: index, ceiling: count-1)
        // 3.
        array.swapAt(index, destination)
    }
}

// 4.
func getRandom(floor: Int, ceiling: Int) -> Int {
    return Int.random(in: floor...ceiling)
}

Explanations:

1. Let’s iterate with all elements of the array.

let count = array.count
for index in 0..<count {

2. Let’s find a destination index with the helper function within the range current index to the end of the array.

let destination = getRandom(floor: index, ceiling: count-1)