How would you code a shuffle() function that randomizes an array uniformly using roll()?

Question Analysis

The question asks you to implement a shuffle() function that randomizes an array uniformly. The constraint here is to use a function called roll(). This implies that roll() is a predefined or primitive function available to you, which likely simulates rolling a die or generating a random number within a specific range.

The objective is to shuffle the elements of the array such that each permutation is equally likely, which means implementing a uniform random shuffle. This is commonly achieved using the Fisher-Yates shuffle algorithm (also known as the Knuth shuffle).

Answer

To implement a shuffle() function using roll(), you can use the Fisher-Yates shuffle algorithm. Here's a possible implementation in Python, assuming roll(n) returns a random integer between 0 and n-1:

import random

def roll(n):
    # Assuming roll(n) returns a random integer from 0 to n-1
    return random.randint(0, n-1)

def shuffle(array):
    n = len(array)
    for i in range(n - 1, 0, -1):
        # Get a random index from 0 to i
        j = roll(i + 1)
        # Swap elements at i and j
        array[i], array[j] = array[j], array[i]

# Example usage
arr = [1, 2, 3, 4, 5]
shuffle(arr)
print(arr)

Explanation:

• Fisher-Yates Algorithm: It iterates over the array from the last element down to the second element.
• Random Index Selection: For each position i, it selects a random index j between 0 and i using the roll() function.
• Element Swap: It swaps the elements at indices i and j.
• Uniform Shuffle: This algorithm ensures that all permutations of the array are equally likely, providing a uniform shuffle.

This approach efficiently shuffles the array in-place with a time complexity of O(n), where n is the number of elements in the array.