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.

Source: codewars | Difficulty: MEDIUM_HARD
Tags: Fundamentals

Starter code: def prod(u):
	

Solutions:
def prod(n):
	ret = [{1.0}]
	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}'


_elements = []

def _cgt(arr, pos):
	if pos + 1 < len(arr) and arr[pos + 1] == 1:
		if pos == 0 or arr[pos - 1] >= arr[pos] + 1:
			_gt(arr[:pos] + [arr[pos] + 1] + arr[pos + 2:], pos)

def _gt(arr, pos):
	nonlocal _elements
	_elements.append(arr)
	_cgt(arr, pos)
	_cgt(arr, pos + 1)
	return

def gt(num):
	nonlocal _elements
	_elements = []
	_gt([1] * num, 0)
	return _elements

def part(N):
	products = {}
	for arr in gt(N):
		prod = arr[0]
		for v in arr[1:]:
			prod *= v
		products[prod] = True
	pds = sorted((p for p in products))
	r = pds[-1] - 1
	a = sum(pds) / float(len(pds))
	m = (pds[len(pds) / 2] + pds[(len(pds) - 1) / 2]) / 2.0
	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

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
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 = {}

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)