Random Subset explanation-CodePudding

I am having a bit trouble understanding the solutions to elements of programming interviews in python q - 5.15 Questions: Compute a random subset with equal probabilty give n - the range of rand numbers and k - the size of subset

this is my solution which is incorrect

import random
n = 5
k = 2
elem = {}
for i in range(k):
    rand_idx = random.randrange(i, n)
    elem[i] = rand_idx
    elem[rand_idx] = i

print(elem)
solutions = []
for i in range(k):
    solutions.append(elem[i])

The solutions from author is

def random_subset(n: int, k: int) -> List[int]:
    changed_elements: Dict [int, int] = {}
    for i in range(k):
        rand_idx = random.randrange(i,n)
        rand_idk_mapped = changed_elements.get(rand_idx,rand_idx)
        i_mapped = changed_elements.get(i, i)
        changed_elements [rand_idx] = i_mapped
        changed_elements[i] = rand_idk_mapped


    solutions = []
    print(changed_elements)
    for i in range(k):
        solutions.append(changed_elements[i])

    return solutions

Could someone pls example what is going on in the authors code. And also what this means.

changed_elements: Dict [int, int] = {} '' #vs changed_elements = {}

Thanks, I am new programmer.

CodePudding user response：

The expression Dict [int, int] is a type annotation. It indicates that changed_elements is a dictionary with integer keys and integer values.

CodePudding user response：

Ahh ok it makes sense now

    rand_idk_mapped = changed_elements.get(rand_idx,rand_idx)
    i_mapped = changed_elements.get(i, i)
    changed_elements [rand_idx] = i_mapped
    changed_elements[i] = rand_idk_mapped

Case 1: nothing exists, create a new key value pair
map rand_idx -> i
map i -> rand_idk

Case 2: rand_idx exists, get its value rand_idx_mapped
map rand_idx_mapped -> i
map i -> rand_idx_mapped

Case 3: i exists, get its value i_mapped
map rand_idx_mapped -> i_mapped
map i -> rand_idx

Case 4: case2 and case3
map rand_idx_mapped -> i_mapped
map i -> rand_idx_mapped

Note:
changed_elements.get(a,x) - > is a exist return its value else returns x