"math function library"
def fact(n):
'''-> n-factorial computed iteratively in a for loop
O(n) time, O(1) space'''
pass
def fact2(n):
'''-> n-factorial computed iteratively in a while loop
O(n) time, O(1) space'''
pass
def factR(n):
'''-> n-factorial computed recursively
O(n) time, O(n) space as python cannot optimize recursion'''
pass
def fact1(n):
'''-> n-factorial computed by a single line of code
O(n) time, O(1) space'''
pass
def fib(n):
'''-> nth Fibonacci number computed iteratively
O(n) time, O(1) space'''
pass
def fibs(n):
'''Generator function yielding the Fibonacci numbers up to fib(n)
O(n) time, O(1) space'''
pass
def fibR(n):
'''-> nth Fibonacci number computed with 2 recursive calls
what's bad about this algorithm?'''
pass
def rPascal(L):
'''given nth row of Pascal's triangle as a list L -> (n+1)th row
O(len(L)) time and space'''
pass
def rPascal1(L):
'''single line version of rPascal
O(len(L)) time and space'''
pass
def tPascal(n):
'''-> first n+1 rows of Pascal's triangle as a list of lists
the nth row represents the binomial coefficients of (x+y)**n
O(n**2) time and space'''
pass
def tPascal1(n):
'''single line version of tPascal which reuses rPascal1
O(n**2) time and space'''
pass
def getCombinationsFunc(maxN):
'''-> a function c(n, k) where n must be passed a value <= maxN
c(n, k) -> the number of ways to choose k items from a set of size n
getCombinationsFunc(maxN) = O(maxN**2) time and space
c(n, k) = O(1) time and space'''
pass
def permutations(n, k):
'''-> number of ways to order r items chosen from a set of size n
O(k) time, O(1) space'''
pass
# accept_sequence(f) is a decorator for any function f(*args)
# -> a function w(*args) such that:
# w(one_iterable_argument) -> f(argument_unpacked)
# otherwise, w(*args) -> f(*args)
# accept_sequence(f) = O(1) time and space
# w has identical time and space complexity to f'''
def accept_sequence(f): # EXTRA CREDIT
pass
def is_iterable(obj): # EXTRA CREDIT - helps with accept_sequence
'''-> True or False depending on whether obj is iterable
O(1) time and space'''
pass
def powerList(*args):
'''-> a list of tuples representing all possible subsets of args
O(2**len(args)) time and space'''
pass
def powerList1(*args):
'''single line version of powerList
O(2**len(args)) time and space'''
pass
def permuteSetR(*args): # EXTRA CREDIT
'''-> every permutation of args as a list of tuples computed recursively
O(n(n!))) time and space, where n = len(args)'''
pass
def permuteSetG(*args): # EXTRA CREDIT
'''Generator function yields each permutation of args.
O(n(n!)) time, O(n) or O(n**2) space, where n = len(args)'''
pass
def perms1(S): # EXTRA EXTRA CREDIT, 80 character limit relaxed
'''-> every permuataion of elements of S. Single line version.
O(n(n!))) time and space, where n = len(S)'''
pass
if __name__ == '__main__':
# PUT YOUR TESTING CODE HERE
print "testing mathtools module"