You should have done Product Partitions I to do this second part.
If you solved it, you should have notice that we try to obtain the multiplicative partitions with ```n ≤ 100 ```.

In this kata we will have more challenging values, our ```n ≤  10000```. So, we need a more optimized a faster code.

We need the function ```prod_int_partII()``` that will give all the amount of different products, excepting the number itself multiplied by one.

The function ```prod_int_partII()``` will receive two arguments, the number ```n``` for the one we have to obtain all the multiplicative partitions, and an integer s that determines the products that have an amount of factors equals to ```s```.

The function will output a list with this structure:
```python
[(1), (2), [(3)]]

(1) Total amount of different products we can obtain, using the factors of n. (We do not consider the product n . 1)

(2) Total amount of products that have an amount of factors equals to s.

[(3)] A list of lists with each product represented with by a sorted list of the factors. All the product- lists should be sorted also.
If we have only one product-list as a result, the function will give only the list 
and will not use the list of lists
```
Let's see some cases:
```python
prod_int_partII(36, 3) == [8, 3, [[2, 2, 9], [2, 3, 6], [3, 3, 4]]]

/// (1) ----> 8 # Amount of different products, they are: [2, 2, 3, 3], [2, 2, 9], 
[2, 3, 6], [2, 18], [3, 3, 4], [3, 12], [4, 9], [6, 6] (8 products)
    
    (2) ----> 3 # Amount of products with three factors (see them bellow)

    (3) ----> [[2, 2, 9], [2, 3, 6], [3, 3, 4]] # These are the products with 3 factors
```
```python
prod_int_partII(48, 5) == [11, 1, [2, 2, 2, 2, 3]] # Only one list.
```
Again consider that some numbers will not have multiplicative partitions.
```python
prod_int_partII(37, 2) == [0, 0, []]
```
Happy coding!!

(Recursion is advisable)

Difficulty: EASY
Tags: Fundamentals

Data structures

Mathematics

Complete search
Skill types: Data structures

Complete search

Starter code:
def prod_int_partII(n, s):
	

Solutions:
def prod_int_partII(n, s, min_=2):
	(total, fac) = (0, [])
	for d in range(min_, int(n ** 0.5) + 1):
		if not n % d:
			(count, l, sub) = prod_int_partII(n // d, s - 1, d)
			if l == 1:
				sub = [sub]
			total += count + 1
			fac.extend(([d] + x for x in sub))
	if s == 1:
		fac = [[n]]
	return [total, len(fac), fac[0] if len(fac) == 1 else fac]


from functools import reduce

def updateParts(d, s, n, p):
	d.append(p)
	for t in list(s):
		s.add(tuple(sorted(t + (p,))))
		for i in range(len(t)):
			s.add(tuple(sorted(t[:i] + (p * t[i],) + t[i + 1:])))
	s.add((p,))
	return n // p

def prod_int_partII(n, m):
	(x, d, s, p) = (n, [], set(), 2)
	while p * p <= n:
		while not n % p:
			n = updateParts(d, s, n, p)
		p += 1 + (p != 2)
	if n - 1 and n != x:
		updateParts(d, s, -1, n)
	s = [t for t in s if reduce(int.__mul__, t) == x and len(t) > 1]
	d = sorted((list(t) for t in s if len(t) == m))
	return [len(s), len(d), d[0] if len(d) == 1 else d]


def prod_int_partII(n, s):
	part = list(mul_part_gen(n))[:-1]
	sub = [p for p in part if len(p) == s]
	return [len(part), len(sub), sub[0] if len(sub) == 1 else sub]

def mul_part_gen(n, k=2):
	if n == 1:
		yield []
	for i in range(k, n + 1):
		if n % i == 0:
			for part in mul_part_gen(n // i, i):
				yield ([i] + part)


div = lambda n: [[i, n // i] for i in range(2, int(n ** 0.5) + 1) if not n % i]

def prod_int_partII(n, s):
	(li, parts) = (div(n), set())

	def recur(li, s=[]):
		parts.add(tuple(sorted(s)))
		for i in li:
			recur(div(i[1]), s + i if not s else s[:-1] + i)
	recur(li)
	req = sorted(filter(lambda x: len(x) == s, parts))
	return [len(parts) - 1, len(req), list([map(list, req), req[0]][len(req) == 1]) if req else []]


from math import sqrt

def partitions(n, floor=2):
	parts = [[n]]
	for i in range(floor, int(sqrt(n)) + 1):
		if n % i == 0:
			for part in partitions(n // i, i):
				parts.append([i] + part)
	return parts

def prod_int_partII(n, s):
	lists = []
	parts = partitions(n, 2)
	for part in parts:
		if len(part) == s:
			lists.append(part)
	if len(lists) == 1:
		list = lists[0]
	else:
		list = lists
	return [len(parts) - 1, len(lists), list]


def prod_int_partII(n, s):
	comb = set()
	for p in partition(n):
		if len(p) > 1:
			comb.add(tuple(sorted(p)))
	res = sorted([p for p in comb if len(p) == s])
	return [len(comb), len(res), list(res[0]) if len(res) == 1 else [list(t) for t in res]]

def partition(n, start=2):
	if n == 1:
		yield []
	for i in range(start, n + 1):
		if n % i == 0:
			for p in partition(n // i, i):
				yield (p + [i])


def p(n, z=2):
	r = []
	s = 0
	for i in range(z, int(n ** 0.5) + 1):
		if n % i == 0:
			(x, y) = p(n // i, i)
			s += x + 1
			r += [[i] + v for v in y] + [[i, n // i]]
	return (s, r)

def prod_int_partII(n, l):
	(s, r) = p(n)
	x = [v for v in r if len(v) == l]
	L = len(x)
	if L == 1:
		x = x[0]
	return [s, L, x]


def prod_int_partII(n, s):
	res = []
	stack = [[n, 2, []]]
	while stack:
		(m, d, store) = stack.pop(0)
		for i in range(d, int(m ** 0.5) + 1):
			if m % i == 0:
				res.append(store + [i] + [m // i])
				stack.append([m // i, i, store + [i]])
	filtred_res = list(filter(lambda x: len(x) == s, res))
	if filtred_res:
		return [len(res), len(filtred_res), filtred_res] if len(filtred_res) > 1 else [len(res), len(filtred_res), filtred_res[0]]
	else:
		return [len(res), 0, []]


from collections import defaultdict
from itertools import islice

def primes():
	yield 2
	D = defaultdict(list)
	i = 3
	while True:
		if i not in D:
			D[i * i].append(i)
			yield i
		else:
			for k in D[i]:
				j = i + k
				while j % 2 == 0:
					j += k
				D[j].append(k)
			del D[i]
		i += 2
PRIMES = list(islice(primes(), 1000))

def decompose(n):
	r = defaultdict(int)
	for p in PRIMES:
		while n % p == 0:
			r[p] += 1
			n //= p
		if n == 1:
			break
	return r

def prod_int_partII(n, s):
	r = []
	d = decompose(n)
	ds = [i for i in range(2, n) if n % i == 0]
	total = sum((i for (_, i) in list(d.items())))
	q = defaultdict(list)

	def aux(m, ci, c, i=0, p=[]):
		if c == 0:
			if m == 1:
				q[ci].append(p)
			return
		else:
			for j in range(i, len(ds)):
				if m % ds[j] == 0:
					aux(m // ds[j], ci, c - 1, j, p + [ds[j]])
	for i in range(2, total + 1):
		aux(n, i, i)
	return [sum((len(i) for i in list(q.values()))), len(q[s]), q[s][0] if len(q[s]) == 1 else q[s]]