[Python] How to create possible sets of n numbers from m-sized prime number list?

I have a list of m elements (prime numbers) and I want to create all possible sets of n numbers which fulfil certain conditions:

• the maximum number of each set should be below a certain threshold value t
• the numbers in each set should be unique

So, my thoughts:

1. split the m-sized list into all possible n subsets
2. calculate the product of each subset
3. exclude duplicate sets, sets with duplicates and sets with maximum above the threshold

Searching StackOverflow I found this: How to get all possible combinations of dividing a list of length n into m sublists

Taking the partCombo from here and add some more lines, I ended up with this:

Script:

### get set of numbers from prime number list
from itertools import combinations

def partCombo(L,N=4): # https://stackoverflow.com/a/66120649
if N==1: yield [L]; return
for size in range(1,len(L)-N+2):
for combo in combinations(range(len(L)),size): # index combinations
part = list(L for i in combo) # first part
remaining = list(L)
for i in reversed(combo): del remaining # unused items
yield from ([part]+rest for rest in partCombo(remaining,N-1))

def lst_product(lst):
p = 1
for i in range(len(lst)):
p *= lst
return p

a = [2,2,2,2,3,3,5]
n = 3 # number of subsets
t = 50 # threshold for max.
d = sorted([u for u in set(tuple(v) for v in [sorted(list(w)) for w in set(tuple(z) for z in [[lst_product(y) for y in x] for x in partCombo(a, N=n) ])]) if max(u)<t])
print(len(d))
print(d)
### end of script


Result: (for a = [2,2,2,2,3,3,5], i.e. m=7; n=3, t=50)

26
[(2, 8, 45), (2, 9, 40), (2, 10, 36), (2, 12, 30), (2, 15, 24), (2, 18, 20), (3, 5, 48), (3, 6, 40), (3, 8, 30), (3, 10, 24), (3, 12, 20), (3, 15, 16), (4, 4, 45), (4, 5, 36), (4, 6, 30), (4, 9, 20), (4, 10, 18), (4, 12, 15), (5, 6, 24), (5, 8, 18), (5, 9, 16), (5, 12, 12), (6, 6, 20), (6, 8, 15), (6, 10, 12), (8, 9, 10)]


This is fast and I need to also exclude the sets having duplicate numbers, e.g. (4,4,45), (5,12,12), (6,6,20)

Here comes the problem:

If I have a list, e.g. a = [2,2,2,2,2,2,2,3,5,5,7,13,19], i.e. m=13 and n=6, the combinations are quickly getting into the millions/billions, but there are millions of duplicates which I would like to exclude right from the beginning. Also the threshold t will exclude a lot of combinations. And maybe just a few hundreds sets will remain.

If I start the script with the above values for (a, m=13, n=6), the script will take forever... Is there maybe a smarter way to reduce/exclude a lot of duplicate combinations and achieve this in a much faster way or some smart Python feature which I am not aware of?

Continue reading...