#!/usr/bin/env python import random import timeit def rand(m, n): return random.randint(m, n) def getDuplicates(numbers): nset = set() duplicates = set() for num in numbers: if num in nset: duplicates |= { num } else: nset |= { num } return duplicates def checkSolutionContract(a, b, N): s = b - a assert a < b assert s >= N def solutionOne(a, b, N): numbers = [] while len(numbers) < N: num = rand(a, b) if num not in numbers: numbers.append(num) return numbers def solutionTwo(a, b, N): possible = [ x for x in range(a, b + 1) ] numbers = [] while len(numbers) < N: num = rand(0, len(possible) - 1) numbers.append(possible[num]) possible.remove(possible[num]) return numbers def solutionThree(a, b, N): possible = [ x for x in range(a, b + 1) ] shuffle(possible) return possible[0:N] # return first N elements def shuffle(arr): # Fisher-Yates shuffle for i in range(0, len(arr) - 1): j = rand(i, len(arr) - 1) # swap i-th and j-th element tmp = arr[i] arr[i] = arr[j] arr[j] = tmp def solutionFour(a, b, N): s = b - a possible = { } # map, int -> int numbers = [] for i in range(0, N + 1): num = rand(i, s - 1) if i not in possible: possible[i] = i if num not in possible: possible[num] = num numbers.append(possible[num] + a) tmp = possible[i] possible[i] = possible[num] possible[num] = tmp return numbers def testSolution(solution, a, b, N, passes = 10000): checkSolutionContract(a, b, N) for i in range(0, passes): numbers = solution(a, b, N) duplicates = getDuplicates(numbers) assert len(duplicates) == 0, "%s have duplicates" % (duplicates) def benchmarkSolution(solution, a, b, N): timer = timeit.Timer(lambda: solution(a, b, N)) return timer.timeit(number = 100000) def testSolutions(a, b, N): checkSolutionContract(a, b, N) print("testing solutions on: [%s, %s], N = %s" % (a, b, N)) print("testing solution one...") testSolution(solutionOne, a, b, N) print("\tdone") print("testing solution two...") testSolution(solutionTwo, a, b, N) print("\tdone") print("testing solution three...") testSolution(solutionThree, a, b, N) print("\tdone") print("testing solution four...") testSolution(solutionFour, a, b, N) print("\tdone") def benchmarkSolutions(a, b, N): checkSolutionContract(a, b, N) print("benchmarks on: [%s, %s], N = %s" % (a, b, N)) print("\t one: %s" % (benchmarkSolution(solutionOne, a, b, N))) print("\t two: %s" % (benchmarkSolution(solutionTwo, a, b, N))) print("\tthree: %s" % (benchmarkSolution(solutionThree, a, b, N))) print("\t four: %s" % (benchmarkSolution(solutionFour, a, b, N))) parameters = [ (0, 99, 10), (0, 99, 50), (0, 99, 90), (0, 9999, 10), (0, 9999, 500), (0, 9999, 5000), (0, 9999, 9000), ] testParameters = random.choice(parameters) testSolutions(*testParameters) for params in parameters: benchmarkSolutions(*params)