### Functional Python

Due September 23rd by midnight

### Objectives

Practice functional programming with Python. Write concise and efficient algorithms in Python and package them together as a function library.

### Description

Your job is to code up a library of handy mathematical functions in a module called `mathtools`

. The specifications for all the functions have already been entered in the file mathtools.py in which your code should replace the `pass`

statement in each function body. The first line of each function is a documentation string used by Python's `help`

function. At the interactive prompt try `import mathtools`

and then `help(mathtools)`

. One function, a decorator function called `accept_sequence`

, does not and should not have its own documentation string for reasons that will become apparent if you do the extra credit part of this assignment. At the end of the file is a place for your testing code. This code will only execute if `mathtools`

is run as the main program, not when it is imported. **Testing your functions thoroughly before you submit them is extremely important and the quality of your test code will affect your score.**

If you are not already familiar with the Factorial function, Fibonaci numbers, and Pascal's triangle, you should look at these links for the specifications.

### Other Requirements

- Included in the documentation strings are the required time and space complexity of each function.
- Single line functions (functions whose name ends with '1'):
- Write and test the multiline version first, and only then think about how to shorten it to one line of code which must:
- Be less than 80 characters wide
- Not include semi-colons
- Not call any additional functions you have written (but may call built-ins) unless stated otherwise

`lambda`

,`reduce`

,`zip`

, and list comprehensions may all be useful

- Write and test the multiline version first, and only then think about how to shorten it to one line of code which must:
`getCombinationsFunc`

:- Must not perform any multiplications
- Must return a function that does not perform any multiplications
- Will find Pascal's triangle very helpful

**EXTRA CREDIT**`permuteSet`

and`permuteSetR`

:- There are n! permutations of a set of size n. 10! = 3628800, so the permutations of a set with as few as 10 elements can use a significant amount of memory if computed with
`permuteSetR`

- Writing
`permuteSet`

as an iterative generator function avoids this problem but requires a tricky implementation of depth first search. My implementation is 16 lines long and by far the longest function in`mathtools`

- There are n! permutations of a set of size n. 10! = 3628800, so the permutations of a set with as few as 10 elements can use a significant amount of memory if computed with
- Decorating the
`powerSet`

functions:- These functions accept a variable number of arguments
`*args`

. - The purpose of decorating them is for when they are passed just one argument which happens to be an iterable sequence. The decorator should unpack the sequence so it will be treated as if it were an argument tuple with each element of the sequence becoming a separate argument passed on to the decorated function.
- The
`is_iterable`

function is helpful when writing the`accept_sequence`

decorator. - (This is a lot easier than writing
`permuteSet`

or`permuteSetR`

)

- These functions accept a variable number of arguments

Below is an example trace of how the functions in `mathtools.py`

should work when used in an interactive Python session.

>>> from mathtools import * >>> fact(0) 1 >>> fact(5) 120 >>> fact(10) 3628800 >>> fact(100) 93326215443944152681699238856266700490715968264381621 46859296389521759999322991560894146397615651828625369 7920827223758251185210916864000000000000000000000000L >>> factR(0) 1 >>> factR(100) 93326215443944152681699238856266700490715968264381621 46859296389521759999322991560894146397615651828625369 7920827223758251185210916864000000000000000000000000L >>> fact2(0) 1 >>> fact2(100) 93326215443944152681699238856266700490715968264381621 46859296389521759999322991560894146397615651828625369 7920827223758251185210916864000000000000000000000000L >>> fact1(0) 1 >>> fact1(100) 93326215443944152681699238856266700490715968264381621 46859296389521759999322991560894146397615651828625369 7920827223758251185210916864000000000000000000000000L >>> fib(5) 5 >>> fib(0) 0 >>> fib(20) 6765 >>> fib(100) 354224848179261915075L >>> fibR(20) 6765 >>> fibR(30) 832040 >>> fib(30) 832040 >>> for i in fibs(10): print i ... 0 1 1 2 3 5 8 13 21 34 55 >>> [i for i in fibs(20)] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765] >>> rPascal([1]) [1, 1] >>> rPascal1([1,1]) [1, 2, 1] >>> rPascal1([1,2,1]) [1, 3, 3, 1] >>> rPascal([1,3,3,1]) [1, 4, 6, 4, 1] >>> tPascal(10) [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1], [1, 6, 15, 20, 15, 6, 1], [1, 7, 21, 35, 35, 21, 7, 1], [1, 8, 28, 56, 70, 56, 28, 8, 1], [1, 9, 36, 84, 126, 126, 84, 36, 9, 1], [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1]] >>> tPascal1(10) [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1], [1, 6, 15, 20, 15, 6, 1], [1, 7, 21, 35, 35, 21, 7, 1], [1, 8, 28, 56, 70, 56, 28, 8, 1], [1, 9, 36, 84, 126, 126, 84, 36, 9, 1], [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1]] >>> c = getCombinationsFunc(100) >>> c(0,0) 1 >>> c(1,0) 1 >>> c(1,1) 1 >>> c(5,3) 10 >>> c(12,5) 792 >>> c(60,23) 23385332420868600L >>> c(100,50) 100891344545564193334812497256L >>> permutations(7,5) 2520 >>> permutations(7,1) 7 >>> powerList(1,2,3) [(), (1,), (2,), (1, 2), (3,), (1, 3), (2, 3), (1, 2, 3)] >>> powerList1(1,2,3) [(), (1,), (2,), (1, 2), (3,), (1, 3), (2, 3), (1, 2, 3)] >>> powerList1(1.2, 'hello', False) [(), (1.2,), ('hello',), (1.2, 'hello'), (False,), (1.2, False), ('hello', False), (1.2, 'hello', False)] >>> powerList(1,2,3,4) [(), (1,), (2,), (1, 2), (3,), (1, 3), (2, 3), (1, 2, 3), (4,), (1, 4), (2, 4), (1, 2, 4), (3, 4), (1, 3, 4), (2, 3, 4), (1, 2, 3, 4)] >>> >>> >>> # AND NOW FOR EXTRA CREDIT ... >>> permuteSetR([1,2,3]) [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)] >>> [x for x in permuteSet([1,2,3])] [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)] >>> permuteSetR([1,2,3,4]) [(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2), (2, 1, 3, 4), (2, 1, 4, 3), (2, 3, 1, 4), (2, 3, 4, 1), (2, 4, 1, 3), (2, 4, 3, 1), (3, 1, 2, 4), (3, 1, 4, 2), (3, 2, 1, 4), (3, 2, 4, 1), (3, 4, 1, 2), (3, 4, 2, 1), (4, 1, 2, 3), (4, 1, 3, 2), (4, 2, 1, 3), (4, 2, 3, 1), (4, 3, 1, 2), (4, 3, 2, 1)] >>> for t in permuteSet([1,2,3,4]): ... print t ... (1, 2, 3, 4) (1, 2, 4, 3) (1, 3, 2, 4) (1, 3, 4, 2) (1, 4, 2, 3) (1, 4, 3, 2) (2, 1, 3, 4) (2, 1, 4, 3) (2, 3, 1, 4) (2, 3, 4, 1) (2, 4, 1, 3) (2, 4, 3, 1) (3, 1, 2, 4) (3, 1, 4, 2) (3, 2, 1, 4) (3, 2, 4, 1) (3, 4, 1, 2) (3, 4, 2, 1) (4, 1, 2, 3) (4, 1, 3, 2) (4, 2, 1, 3) (4, 2, 3, 1) (4, 3, 1, 2) (4, 3, 2, 1) >>> powerList('abcd') [(), ('a',), ('b',), ('a', 'b'), ('c',), ('a', 'c'), ('b', 'c'), ('a', 'b', 'c'), ('d',), ('a', 'd'), ('b', 'd'), ('a', 'b', 'd'), ('c', 'd'), ('a', 'c', 'd'), ('b', 'c', 'd'), ('a', 'b', 'c', 'd')] >>> powerList([1,2,3,4]) [(), (1,), (2,), (1, 2), (3,), (1, 3), (2, 3), (1, 2, 3), (4,), (1, 4), (2, 4), (1, 2, 4), (3, 4), (1, 3, 4), (2, 3, 4), (1, 2, 3, 4)] >>> powerList1(xrange(5)) [(), (0,), (1,), (0, 1), (2,), (0, 2), (1, 2), (0, 1, 2), (3,), (0, 3), (1, 3), (0, 1, 3), (2, 3), (0, 2, 3), (1, 2, 3), (0, 1, 2, 3), (4,), (0, 4), (1, 4), (0, 1, 4), (2, 4), (0, 2, 4), (1, 2, 4), (0, 1, 2, 4), (3, 4), (0, 3, 4), (1, 3, 4), (0, 1, 3, 4), (2, 3, 4), (0, 2, 3, 4), (1, 2, 3, 4), (0, 1, 2, 3, 4)] >>>

Put your program in a file called `mathtools.py`

.
**Advice: Keep an eye on the class discussion
board for helpful hints on how to do this assignment!**

### Grading Criteria

Your functions will be graded on correctness, efficiency, and brevity of code. You should also attempt to make your code easy to read.

### Submission Checklist

`mathtools.py`