473 Homework 5 #1a Python Code

part1a.py

import random

def Random(n):
  return random.randint(1,n)

def get_k_samples(S, k):
  samples = []
  for i in range(k):
    samples.append(S.pop())
  l = k
  while len(S)>0:
    x = S.pop()
    l = l+1
    if Random(l) <= k:
      samples[Random(k)-1] = x
  return set(samples)



###################################################################
###################################################################
####################### Testing it out: ###########################
###################################################################
###################################################################

from pprint import pprint #For pretty printing dictionaries
from collections import Counter #For counting how many times each
                                #  combination occurs in my samples
                            
# Test it out with 100,000 calls
trial_data = [get_k_samples(range(6),3) for it in range(100000)]

trial_data_as_strings = map(str, trial_data)
counted = Counter(trial_data_as_strings)
counted_as_dict = dict(counted)
pprint(counted_as_dict)

Pseudocode: https://gist.github.com/chrisshroba/178548573b914cc1f8b4