From wikipedia  

In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, 
is a way of writing n as a sum of positive integers. 
Two sums that differ only in the order of their summands are considered the **same** partition.

For example, 4 can be partitioned in five distinct ways:

`4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1`.

We can write:

`enum(4) -> [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]]` and

`enum(5) -> [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]]`.

The number of parts in a partition grows very fast.
For n = 50 number of parts is `204226`, for 80 it is `15,796,476`
It would be too long to tests answers with arrays of such size. So our task is the following:

1 - n being given (n integer, 1 <= n <= 50) calculate enum(n) ie the partition of n.
We will obtain something like that:  
`enum(n) -> [[n],[n-1,1],[n-2,2],...,[1,1,...,1]]` (order of array and sub-arrays
doesn't matter). This part is not tested.

2 - For each sub-array of enum(n) calculate its product. 
If n = 5 we'll obtain **after removing duplicates and sorting**:

`prod(5) -> [1,2,3,4,5,6]`

`prod(8) -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 15, 16, 18]`

If n = 40 prod(n) has a length of `2699` hence the tests will not verify such arrays.
Instead our task number 3 is:

3 - return the range, the average and the median of prod(n) in the following form 
(example for n = 5):

`"Range: 5 Average: 3.50 Median: 3.50"`

Range is an integer, Average and Median are float numbers rounded to two decimal 
places (".2f" in some languages).

#Notes:
`Range` : difference between the highest and lowest values. 

`Mean or Average` : To calculate mean, add together all of the numbers 
in a set and then divide the sum by the total count of numbers.

`Median` : The median is the number separating the higher half 
of a data sample from the lower half. 
(https://en.wikipedia.org/wiki/Median)

#Hints:
Try to optimize your program to avoid timing out.

Memoization can be helpful but it is not mandatory for being successful.

Difficulty: interview

Starter code:

def prod(u):
	

Solutions:
def prod(n):
    ret = [{1.}]
    for i in range(1, n+1):
        ret.append({(i - x) * j for x, s in enumerate(ret) for j in s})
    return ret[-1]

def part(n):
    p = sorted(prod(n))
    return "Range: %d Average: %.2f Median: %.2f" % \
            (p[-1] - p[0], sum(p) / len(p), (p[len(p)//2] + p[~len(p)//2]) / 2)

from functools import reduce
def prod(u):
    p = 1
    for x in u:
        p *= x
    return p

cache = {}
def part_aux(s, k):
    k0 = min(s, k)
    if k0 < 1:
        return []
    i = (s - 1) * s / 2 + k0 - 1
    ret = cache.get(i)
    if ret:
        return ret
    res = []
    for n in range(k0, 0, -1):
        r = s - n
        if (r > 0):
            for t in part_aux(r, n):
                if type(t) is list: 
                    res.append([n] + t)
                else: res.append([n, t])
        else:
            res.append([n])
    cache[i] = res
    return res

def part(n):
    r = sorted(set(map(prod, part_aux(n, n))))
    lg = len(r)
    avg = reduce(lambda x, y : x + y, r, 0)  / float(lg)
    rge = r[lg - 1] -  r[0]
    md = (r[(lg - 1) // 2] + r[lg // 2]) / 2.0
    return "Range: %d Average: %.2f Median: %.2f" % (rge, avg, md)


from functools import lru_cache, reduce
from operator import or_
from statistics import mean, median

@lru_cache(maxsize=None)
def prod(n, x):
    if n < 0:
        return set()
    return reduce(or_, ({i*s for s in prod(n-i, i)} for i in range(2, x+1)), {1})

def part(n):
    xs = prod(n, n)
    return f"Range: {max(xs) - min(xs)} Average: {mean(xs):.2f} Median: {median(xs):.2f}"

# List of generated elements
_elements = []


def _cgt(arr, pos):
    # Check if element isn't last
    # And element next to it is equal to 1(ONE)
    if pos + 1 < len(arr) and arr[pos + 1] == 1:
        # Check if current element is not bigger than previous one
        # Because we want to get sorted array
        # without repetitions
        if pos == 0 or arr[pos - 1] >= arr[pos] + 1:
            # If all conditions are met - creating new array
            # and calling recursive function with it
            _gt(arr[:pos] + [arr[pos] + 1] + arr[pos + 2:], pos)

def _gt(arr, pos):
    nonlocal _elements
    _elements.append(arr) # Add current array of summands

    # Checking 2 elements
    # Example: For array [2, 1, 1] with pos = 0(zero) it will found:
    # array [3, 1] because 3 is first
    # and array [2, 2] because 2nd(second) number 2(two) is not bigger than first
    _cgt(arr, pos)
    _cgt(arr, pos + 1)

    # Exit function without return value
    return


# Function that returning array of summands for given number
def gt(num):
    nonlocal _elements
    # Clear elements array to get right result
    _elements = []
    # Start with array of 1s(ones) and position = 0(zero)
    _gt([1] * num, 0)
    # Return generated elements
    return _elements


def part(N):
    # Create new dictionary that will contain all products
    products = {}
    
    # Find product for each possible array of summands
    for arr in gt(N):
        prod = arr[0]
        for v in arr[1:]: prod *= v
        products[prod] = True
    
    # Sort found products to be able to find median
    pds = sorted(p for p in products)

    # Find values range
    r = pds[-1] - 1
    # Find average of array
    a = sum(pds) / float(len(pds))
    # Find array's median value
    m = (pds[len(pds) / 2] + pds[(len(pds) - 1) / 2]) / 2.0

    # Return formated info about sequence
    return 'Range: %i Average: %.2f Median: %.2f' % (r, a, m)

def part(n):
    p = sorted(set([prod(s) for s in parts(n)]))
    r = max(p) - min(p)
    a = sum(p) / float(len(p))
    m = (p[(len(p)-1)//2] + p[len(p)//2]) / 2.0
    return 'Range: {} Average: {:.2f} Median: {:.2f}'.format(r, a, m)
    
def prod(l):
    p = 1
    for i in l:
        p *= i
    return p
    
# http://jeromekelleher.net/generating-integer-partitions.html    
# No recursion
def parts(n):
    a = [0] * (n + 1)
    k = 1
    a[1] = n
    while k:
        x = a[k - 1] + 1
        y = a[k] - 1
        k -= 1
        while x <= y:
            a[k] = x
            y -= x
            k += 1
        a[k] = x + y
        yield a[:k + 1]

from functools import reduce
from statistics import median
def partition(n, I=1):
    yield (n,)
    for i in range(I, n//2 + 1):
        for p in partition(n-i, i):
            yield (i,) + p

def part(n):
    prod = set()
    all = partition(n)
    for i in all:
        prod.add(reduce(lambda a, b: a*b, i))
    return("Range: {0} Average: {1:.2f} Median: {2:.2f}".format(max(prod) - min(prod), sum(prod)/len(prod), median(prod)))

from functools import reduce
def prod(u):
    p = 1
    for x in u:
        p *= x
    return p

cache = {}
def part_aux(s, k):
    k0 = min(s, k)
    if k0 < 1:
        return []
    i = (s - 1) * s / 2 + k0 - 1
    ret = cache.get(i)
    if ret:
        return ret
    res = []
    for n in range(k0, 0, -1):
        r = s - n
        if (r > 0):
            for t in part_aux(r, n):
                if type(t) is list: 
                    res.append([n] + t)
                else: res.append([n, t])
        else:
            res.append([n])
    cache[i] = res
    return res

def part(n):
    from functools import reduce
    r = sorted(set(map(prod, part_aux(n, n))))
    lg = len(r)
    avg = reduce(lambda x, y : x + y, r, 0)  / float(lg)
    rge = r[lg - 1] -  r[0]
    md = (r[(lg - 1) // 2] + r[lg // 2]) / 2.0
    return "Range: %d Average: %.2f Median: %.2f" % (rge, avg, md)


from functools import reduce
import numpy as np

idx = 0
prods = set([])

def enum(buf, n, min_factor = 1):
    nonlocal idx, prods
    if len(buf)<n:
        buf = [0 for i in range(n)]
    if n <=0:
        prods.add(reduce(lambda x,y:x*y,buf[:idx]))
    else:
        for i in range(min_factor,n+1):
            buf[idx]=i
            idx += 1
            enum(buf, n-i, i)
            idx -= 1

def part(n):
    nonlocal prods,idx
    buf = []
    enum(buf,n)
    ran = max(prods)-min(prods)
    mean = np.mean(list(prods))
    median = np.median(list(prods))
    prods = set([])
    idx = 0    
    return "Range: {} Average: {:.2f} Median: {:.2f}".format(ran,mean,median)

from operator import mul
from functools import reduce


mem = {}


# simple cache for python 2.7
def cache(func):
    def wrap(n):
        if n in mem:
            return mem[n]
        res = func(n)
        mem[n] = res
        return res
    return wrap


@cache
def int_partition(n):
    if n in mem:
        return mem[n]
    if n == 1:
        return {(1,)}
    part_set = int_partition(n - 1)
    result = set()
    for part in list(part_set):
        num_set = set(part)
        for num in num_set:
            tmp = list(part)
            i = part.index(num)
            tmp[i] += 1
            result.add(tuple(tmp))
        result.add(part + tuple([1]))
    return result


def part(n):
    res = {}
    part_set = int_partition(n)
    prod_set = set()
    for part_one in part_set:
        prod_set.add(reduce(mul, part_one, 1))
    prod_list = sorted(list(prod_set))
    
    res['range'] = prod_list[-1] - prod_list[0]
    res['avg'] = float(sum(prod_list)) / len(prod_list)
    mid = int((float(len(prod_list) - 1) / 2))
    rev_mid = -mid if mid else None
    mid_slice = prod_list[mid:rev_mid]
    res['median'] = float(sum(mid_slice)) / len(mid_slice)
    
    tmpl = 'Range: {range} Average: {avg:.2f} Median: {median:.2f}'
    return tmpl.format(**res)

# from timeit import timeit
# print(timeit(partial(part, 40), number=100))