Comment on page
Random Set
17.3 Random Set: Write a method to randomly generate a set of m integers from an array of size n. Each element must have equal probability of being chosen.
The Idea: First lets think of some possible approaches. If n = m, then it is just a shuffle and returning the shuffled array of elements. Otherwise if m < n, we can return [0-m] needed elements from this array. This would be O(N) time, but highly wasteful if we wanted to chose 1 element from an array of size 1 million.
Instead what we could do is randomly generate an index between
[0 - N], append this number to the result array, and then swap the last element with this chosen index in the array. Then our range of next possible elements to chosen from becomes [0-(N-1)]. For the next element, repeat the same process as between, but now swap with N-2, and so fourth.Complexity: O(n) time where n is the number of elements to generate. O(1) extra space
from random import randrange
def rand_set(nums, n):
if n > len(nums):
raise ValueError("Cannot extract that many elements")
else:
rand_elements = []
back_iter = len(nums)
for i in range(0, n):
# generate a random index between 0 and the length of the list
# decrement by 1 every time to ignore elements moved to the back
rand_i = randrange(0, back_iter)
rand_n = nums[rand_i]
# add the result, and move it to the end of the list
rand_elements.append(rand_n)
nums[rand_i], nums[back_iter - 1] = nums[back_iter - 1], nums[rand_i]
back_iter -= 1
return rand_elements
nums = [0, 3, 6789, 6, 7, 8, 9, 34, 43, 45, 567, 56, 65, 46789, 78, 978, 83, 89, 90, 6878, 7654, 245, 765]
for i in range(0, len(nums)):
print(rand_set(nums, i))
Last modified 4yr ago