Scribd
Upload
2 views1 page

Random Sample Algorithm

The document describes a randomized algorithm for selecting a random sample of k elements from an array of n distinct positive numbers using a modified Fisher-Yates shuffle. The algorithm runs in O(n) time and is proven correct through induction, ensuring uniform randomness in selection. It is noted that the method is destructive, altering the original array, and copying it would also take O(n) time.

Uploaded by

Ikhlas Khan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views1 page

Random Sample Algorithm

The document describes a randomized algorithm for selecting a random sample of k elements from an array of n distinct positive numbers using a modified Fisher-Yates shuffle. The algorithm runs in O(n) time and is proven correct through induction, ensuring uniform randomness in selection. It is noted that the method is destructive, altering the original array, and copying it would also take O(n) time.

Uploaded by

Ikhlas Khan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

5/19/23, 1:20 AM Random Sample Algorithm

**You:**

Let A[1..n] be an array of n distinct positive numbers and k ≤ n be some positive integer. Give a randomized
algorithm that return a random sample of k elements from A. The algorithm should run in O(n) time. Prove that
your algorithm is correct and analyze its running time.
------------------
**ChatGPT:**

You can use a modification of the Fisher-Yates or Knuth shuffle algorithm to get a random sample of k elements
from the array. This algorithm works by choosing a random element for each original array position, swapping
the two elements, and then proceeding to the next position.

Here's the modified Fisher-Yates shuffle algorithm:

python Copy code


import random

def random_sample(A, k):


n = len(A)
for i in range(k): # just iterate for k times instead of n
# pick a random index in A from i to n-1
j = [Link](i, n - 1)
# swap A[i] and A[j]
A[i], A[j] = A[j], A[i]
# return the first k elements
return A[:k]

The correctness of this algorithm can be proven by induction. The base case is that for k=1, it selects a random
element uniformly at random. Assume the algorithm works for k, then for k+1, it's equivalent to first drawing k
elements, and then drawing one from the remaining n-k elements, which is exactly the definition of uniformly
random drawing k+1 elements.

The running time is O(n) because the loop runs k times, and each loop iteration performs a constant amount of
work, and then we make a single pass to return the first k elements. Even though the loop runs k times, the time
complexity is still O(n) in the worst-case scenario where k=n.

Note that this is a "destructive" method, which changes the original array. If you want to keep the original array,
you need to copy it first, which also takes O(n) time.

------------------

[Link] 1/1

You might also like