Random Permutation

Problem

Given an array of integers, and an integer index \(k\), randomly permute the array up to index \(k\).

Input

• \(A\) - Array of integers
• \(k\) - integer index representing the indices to permute up to

Approach

Key insights into random permutation with arrays:

• If only k elements are permuted in an array of size n, the algorithm for random permutation should only cost k in time complexity.

• Looping over k elements with an index counter i

  • i should be swapped with a random value that has not been taken. In other words, the random value then should be extracted from \(i ... n\), rather than \(0 ... n\), since values from \(0 ... i\) are already permuted.

• Swapping the original elements into the pool of available random entries \(i ... n\) makes sense.

  • For instance: A = [1, 2, 3, 4, 5], and we want to permute 3 elements:
  • Start at index i=0, and A[0] is swapped with some random number < 5 (since the last array index is 4). Let's say the random number is 3.
  • Now, index i=1. If we look at A, it is now [4, 2, 3, 1, 5].
  • Notice that [4] is the subset of the random permutation we are trying to build, and [2, 3, 1, 5] are available random entries to be used. Since k = 3, not all of these available random entries can be used, which is accurate.

Solution

The following pseudocode implements the basic random permutation subset of a given array, which can be re-used in many ways.

def random_subset(k, A):  
    for i in range(k):
        rand_index = random.randint(i, len(A)-1)  # note the `i` here
        A[i], A[rand_index] = A[rand_index], A[i]
    return A[:k]  # return the permuted subset of A