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))