Search code examples
pythonalgorithmcombinationsprimespython-itertools

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

Input: a list of m prime numbers (with possible repetition), and integers n and t.

Output: all sets of n numbers, where each set is formed by partitioning the input into n parts, and taking the product of the primes in each part. We reject any set containing a number greater than t or any duplicate numbers.
Thanks, @Dave, for the now hopefully clear formulation!

I have a list of m elements (prime numbers) and out of these by using all of them, I want to create all possible sets of n numbers which fulfill certain conditions:

  • the maximum value of each set should be below a certain threshold value t
  • the values 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[i] for i in combo)      # first part
            remaining = list(L)
            for i in reversed(combo): del remaining[i] # 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[i]
    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 larger lists, e.g. a = [2,2,2,2,2,2,2,3,5,5,7,13,19], i.e. m=len(a)=13 and splitting into more subsets n=6, the combinations can quickly get 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?

Clarification:

Thanks for your comments, apparently, I couldn't make my problem clear enough. Let me try to clarify. For example, given the prime number set a = [2,2,2,2,3,3,5] (m=7), I want to make all possible sets of n=3 numbers out of it which satisfy some conditions. So, for example, 5 out of many (I guess 1806) possibilities to split a into 3 parts and the corresponding products of each subset:

  • [2],[2],[2,2,3,3,5] --> (2,2,180): excl. because max=180 > t=50 and duplicate of 2

  • [2],[2,2,2],[3,3,5] --> (2,8,45): included

  • [3],[2,2],[2,2,3,5] --> (3,4,60): excluded because max=60 >t=50

  • [2,2],[2,2],[3,3,5] --> (4,4,45): excluded because duplicates of 4

  • [2,3],[2,3],[2,2,5] --> (6,6,20): excluded because duplicates of 6

Solution

  • This may not be the ultimate most efficient solution, but there are at least two aspects where gains can be made:

    • permutations of the same primes are a wasted effort. It will help to count how many you have of each prime (which will be its maximum exponent) and pre-calculate the partitions you can have of the available exponent into t size tuples. When you have those for each prime, you can think of combining those.

    • Verify the threshold at several stages of the algorithm, also when you have intermediate results. If we imagine involving one prime after the other, and determining the results first for a smaller collection of primes, and then involving the next prime, we can at each stage reject intermediate results that violate the threshold requirement.

    Here is suggested implementation:

    from collections import Counter
from itertools import product, pairwise
from math import log, prod

def gen_partitions(n, num_partitions, min_size, max_size):
    if num_partitions <= 1:
        if num_partitions == 1 and min_size <= n <= max_size:
            yield (n, )
        return
    for i in range(min_size, min(n, max_size) + 1):
        for result in gen_partitions(n - i, num_partitions - 1, min_size, max_size):
            yield (i, ) + result

def solve(primes, tuple_size, threshold):
    # for each distinct prime, get its number of occurrences (which is the exponent for that prime), then
    #    partition that integer into all possible tuple_size partitionings (in any order), and
    #    transform each partitioning (with exponents) to the relevant prime raised to those exponents
    prime_factor_combis = [
        [
            tuple(prime ** exp for exp in exponents)
            for exponents in gen_partitions(count, tuple_size, 0, int(log(threshold, prime)))
        ]
        for prime, count in Counter(primes).items()
    ]
    # Now reduce the list of tuples per prime to a list of tuples having the products.
    # At each step of the reduction:
    #     the next prime is taken into consideration for making the products, and
    #     tuples are removed that have a member that exceeds the threshold
    #     the remaining tuples are made non-decreasing. Also starting with only non-decreasing tuples
    results = [tup for tup in prime_factor_combis[0]
               if all(x <= y for x, y in pairwise(tup))]  # Only keep the non-decreasing 
    for prime_factors in prime_factor_combis[1:]:
        results = set(
            tup
            for p in product(results, prime_factors)
            for tup in [tuple(sorted(map(prod, zip(*p))))]  # assign the accumulated tuple to variable tup
            if tup[-1] < threshold  # remove exceeding values at each iteration of outer loop
        )
    # Finally, remove tuples that contain 1 or that include a repetition of the same number 
    return sorted((result for result in results 
                   if result[0] > 1 and all(x < y for x, y in pairwise(result))))

    You would run it like this for the first example you gave:

    a = [2,2,2,2,3,3,5]
n = 3
t = 50

res = solve(a, n, t)
print("Number of results", len(res))
for tup in res:
    print(tup)

    This outputs:

    Number of results 23
(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, 5, 36)
(4, 6, 30)
(4, 9, 20)
(4, 10, 18)
(4, 12, 15)
(5, 6, 24)
(5, 8, 18)
(5, 9, 16)
(6, 8, 15)
(6, 10, 12)
(8, 9, 10)

    For the input that was said to be a challenge...

    a = [2,2,2,2,2,2,2,3,5,5,7,13,19]
n = 6
t = 50

res = solve(a, n, t)
print("Number of results", len(res))
for tup in res:
    print(tup)

    Output:

    Number of results 385
(2, 4, 35, 38, 39, 40)
(2, 5, 26, 35, 38, 48)
(2, 5, 26, 38, 40, 42)
(2, 5, 28, 38, 39, 40)
(2, 5, 32, 35, 38, 39)
(2, 6, 26, 35, 38, 40)
(2, 7, 20, 38, 39, 40)
(2, 7, 25, 26, 38, 48)
(2, 7, 25, 32, 38, 39)
(2, 7, 26, 30, 38, 40)
(2, 8, 19, 35, 39, 40)
(2, 8, 20, 35, 38, 39)
(2, 8, 25, 26, 38, 42)
(2, 8, 25, 28, 38, 39)
(2, 8, 26, 30, 35, 38)
(2, 10, 13, 35, 38, 48)
(2, 10, 13, 38, 40, 42)
(2, 10, 14, 38, 39, 40)
(2, 10, 16, 35, 38, 39)
(2, 10, 19, 26, 35, 48)
(2, 10, 19, 26, 40, 42)
(2, 10, 19, 28, 39, 40)
(2, 10, 19, 32, 35, 39)
(2, 10, 20, 26, 38, 42)
(2, 10, 20, 28, 38, 39)
(2, 10, 21, 26, 38, 40)
(2, 10, 24, 26, 35, 38)
(2, 10, 26, 28, 30, 38)
(2, 12, 13, 35, 38, 40)
(2, 12, 19, 26, 35, 40)
(2, 12, 20, 26, 35, 38)
(2, 12, 25, 26, 28, 38)
(2, 13, 14, 25, 38, 48)
(2, 13, 14, 30, 38, 40)
(2, 13, 15, 28, 38, 40)
(2, 13, 15, 32, 35, 38)
(2, 13, 16, 25, 38, 42)
(2, 13, 16, 30, 35, 38)
(2, 13, 19, 20, 35, 48)
(2, 13, 19, 20, 40, 42)
(2, 13, 19, 24, 35, 40)
(2, 13, 19, 25, 28, 48)
(2, 13, 19, 25, 32, 42)
(2, 13, 19, 28, 30, 40)
(2, 13, 19, 30, 32, 35)
(2, 13, 20, 21, 38, 40)
(2, 13, 20, 24, 35, 38)
(2, 13, 20, 28, 30, 38)
(2, 13, 21, 25, 32, 38)
(2, 13, 24, 25, 28, 38)
(2, 14, 15, 26, 38, 40)
(2, 14, 16, 25, 38, 39)
(2, 14, 19, 20, 39, 40)
(2, 14, 19, 25, 26, 48)
(2, 14, 19, 25, 32, 39)
(2, 14, 19, 26, 30, 40)
(2, 14, 20, 26, 30, 38)
(2, 14, 24, 25, 26, 38)
(2, 15, 16, 26, 35, 38)
(2, 15, 19, 26, 28, 40)
(2, 15, 19, 26, 32, 35)
(2, 15, 20, 26, 28, 38)
(2, 16, 19, 20, 35, 39)
(2, 16, 19, 25, 26, 42)
(2, 16, 19, 25, 28, 39)
(2, 16, 19, 26, 30, 35)
(2, 16, 21, 25, 26, 38)
(2, 19, 20, 21, 26, 40)
(2, 19, 20, 24, 26, 35)
(2, 19, 20, 26, 28, 30)
(2, 19, 21, 25, 26, 32)
(2, 19, 24, 25, 26, 28)
(3, 4, 26, 35, 38, 40)
(3, 5, 26, 28, 38, 40)
(3, 5, 26, 32, 35, 38)
(3, 7, 20, 26, 38, 40)
(3, 7, 25, 26, 32, 38)
(3, 8, 13, 35, 38, 40)
(3, 8, 19, 26, 35, 40)
(3, 8, 20, 26, 35, 38)
(3, 8, 25, 26, 28, 38)
(3, 10, 13, 28, 38, 40)
(3, 10, 13, 32, 35, 38)
(3, 10, 14, 26, 38, 40)
(3, 10, 16, 26, 35, 38)
(3, 10, 19, 26, 28, 40)
(3, 10, 19, 26, 32, 35)
(3, 10, 20, 26, 28, 38)
(3, 13, 14, 20, 38, 40)
(3, 13, 14, 25, 32, 38)
(3, 13, 16, 19, 35, 40)
(3, 13, 16, 20, 35, 38)
(3, 13, 16, 25, 28, 38)
(3, 13, 19, 20, 28, 40)
(3, 13, 19, 20, 32, 35)
(3, 13, 19, 25, 28, 32)
(3, 14, 16, 25, 26, 38)
(3, 14, 19, 20, 26, 40)
(3, 14, 19, 25, 26, 32)
(3, 16, 19, 20, 26, 35)
(3, 16, 19, 25, 26, 28)
(4, 5, 13, 35, 38, 48)
(4, 5, 13, 38, 40, 42)
(4, 5, 14, 38, 39, 40)
(4, 5, 16, 35, 38, 39)
(4, 5, 19, 26, 35, 48)
(4, 5, 19, 26, 40, 42)
(4, 5, 19, 28, 39, 40)
(4, 5, 19, 32, 35, 39)
(4, 5, 20, 26, 38, 42)
(4, 5, 20, 28, 38, 39)
(4, 5, 21, 26, 38, 40)
(4, 5, 24, 26, 35, 38)
(4, 5, 26, 28, 30, 38)
(4, 6, 13, 35, 38, 40)
(4, 6, 19, 26, 35, 40)
(4, 6, 20, 26, 35, 38)
(4, 6, 25, 26, 28, 38)
(4, 7, 10, 38, 39, 40)
(4, 7, 13, 25, 38, 48)
(4, 7, 13, 30, 38, 40)
(4, 7, 15, 26, 38, 40)
(4, 7, 16, 25, 38, 39)
(4, 7, 19, 20, 39, 40)
(4, 7, 19, 25, 26, 48)
(4, 7, 19, 25, 32, 39)
(4, 7, 19, 26, 30, 40)
(4, 7, 20, 26, 30, 38)
(4, 7, 24, 25, 26, 38)
(4, 8, 10, 35, 38, 39)
(4, 8, 13, 25, 38, 42)
(4, 8, 13, 30, 35, 38)
(4, 8, 14, 25, 38, 39)
(4, 8, 15, 26, 35, 38)
(4, 8, 19, 20, 35, 39)
(4, 8, 19, 25, 26, 42)
(4, 8, 19, 25, 28, 39)
(4, 8, 19, 26, 30, 35)
(4, 8, 21, 25, 26, 38)
(4, 10, 12, 26, 35, 38)
(4, 10, 13, 19, 35, 48)
(4, 10, 13, 19, 40, 42)
(4, 10, 13, 20, 38, 42)
(4, 10, 13, 21, 38, 40)
(4, 10, 13, 24, 35, 38)
(4, 10, 13, 28, 30, 38)
(4, 10, 14, 19, 39, 40)
(4, 10, 14, 20, 38, 39)
(4, 10, 14, 26, 30, 38)
(4, 10, 15, 26, 28, 38)
(4, 10, 16, 19, 35, 39)
(4, 10, 19, 20, 26, 42)
(4, 10, 19, 20, 28, 39)
(4, 10, 19, 21, 26, 40)
(4, 10, 19, 24, 26, 35)
(4, 10, 19, 26, 28, 30)
(4, 10, 20, 21, 26, 38)
(4, 12, 13, 19, 35, 40)
(4, 12, 13, 20, 35, 38)
(4, 12, 13, 25, 28, 38)
(4, 12, 14, 25, 26, 38)
(4, 12, 19, 20, 26, 35)
(4, 12, 19, 25, 26, 28)
(4, 13, 14, 15, 38, 40)
(4, 13, 14, 19, 25, 48)
(4, 13, 14, 19, 30, 40)
(4, 13, 14, 20, 30, 38)
(4, 13, 14, 24, 25, 38)
(4, 13, 15, 16, 35, 38)
(4, 13, 15, 19, 28, 40)
(4, 13, 15, 19, 32, 35)
(4, 13, 15, 20, 28, 38)
(4, 13, 16, 19, 25, 42)
(4, 13, 16, 19, 30, 35)
(4, 13, 16, 21, 25, 38)
(4, 13, 19, 20, 21, 40)
(4, 13, 19, 20, 24, 35)
(4, 13, 19, 20, 28, 30)
(4, 13, 19, 21, 25, 32)
(4, 13, 19, 24, 25, 28)
(4, 14, 15, 19, 26, 40)
(4, 14, 15, 20, 26, 38)
(4, 14, 16, 19, 25, 39)
(4, 14, 19, 20, 26, 30)
(4, 14, 19, 24, 25, 26)
(4, 15, 16, 19, 26, 35)
(4, 15, 19, 20, 26, 28)
(4, 16, 19, 21, 25, 26)
(5, 6, 13, 28, 38, 40)
(5, 6, 13, 32, 35, 38)
(5, 6, 14, 26, 38, 40)
(5, 6, 16, 26, 35, 38)
(5, 6, 19, 26, 28, 40)
(5, 6, 19, 26, 32, 35)
(5, 6, 20, 26, 28, 38)
(5, 7, 8, 38, 39, 40)
(5, 7, 10, 26, 38, 48)
(5, 7, 10, 32, 38, 39)
(5, 7, 12, 26, 38, 40)
(5, 7, 13, 19, 40, 48)
(5, 7, 13, 20, 38, 48)
(5, 7, 13, 24, 38, 40)
(5, 7, 13, 30, 32, 38)
(5, 7, 15, 26, 32, 38)
(5, 7, 16, 19, 39, 40)
(5, 7, 16, 20, 38, 39)
(5, 7, 16, 26, 30, 38)
(5, 7, 19, 20, 26, 48)
(5, 7, 19, 20, 32, 39)
(5, 7, 19, 24, 26, 40)
(5, 7, 19, 26, 30, 32)
(5, 7, 20, 24, 26, 38)
(5, 8, 10, 26, 38, 42)
(5, 8, 10, 28, 38, 39)
(5, 8, 12, 26, 35, 38)
(5, 8, 13, 19, 35, 48)
(5, 8, 13, 19, 40, 42)
(5, 8, 13, 20, 38, 42)
(5, 8, 13, 21, 38, 40)
(5, 8, 13, 24, 35, 38)
(5, 8, 13, 28, 30, 38)
(5, 8, 14, 19, 39, 40)
(5, 8, 14, 20, 38, 39)
(5, 8, 14, 26, 30, 38)
(5, 8, 15, 26, 28, 38)
(5, 8, 16, 19, 35, 39)
(5, 8, 19, 20, 26, 42)
(5, 8, 19, 20, 28, 39)
(5, 8, 19, 21, 26, 40)
(5, 8, 19, 24, 26, 35)
(5, 8, 19, 26, 28, 30)
(5, 8, 20, 21, 26, 38)
(5, 10, 12, 26, 28, 38)
(5, 10, 13, 14, 38, 48)
(5, 10, 13, 16, 38, 42)
(5, 10, 13, 19, 28, 48)
(5, 10, 13, 19, 32, 42)
(5, 10, 13, 21, 32, 38)
(5, 10, 13, 24, 28, 38)
(5, 10, 14, 16, 38, 39)
(5, 10, 14, 19, 26, 48)
(5, 10, 14, 19, 32, 39)
(5, 10, 14, 24, 26, 38)
(5, 10, 16, 19, 26, 42)
(5, 10, 16, 19, 28, 39)
(5, 10, 16, 21, 26, 38)
(5, 10, 19, 21, 26, 32)
(5, 10, 19, 24, 26, 28)
(5, 12, 13, 14, 38, 40)
(5, 12, 13, 16, 35, 38)
(5, 12, 13, 19, 28, 40)
(5, 12, 13, 19, 32, 35)
(5, 12, 13, 20, 28, 38)
(5, 12, 14, 19, 26, 40)
(5, 12, 14, 20, 26, 38)
(5, 12, 16, 19, 26, 35)
(5, 12, 19, 20, 26, 28)
(5, 13, 14, 15, 32, 38)
(5, 13, 14, 16, 30, 38)
(5, 13, 14, 19, 20, 48)
(5, 13, 14, 19, 24, 40)
(5, 13, 14, 19, 30, 32)
(5, 13, 14, 20, 24, 38)
(5, 13, 15, 16, 28, 38)
(5, 13, 15, 19, 28, 32)
(5, 13, 16, 19, 20, 42)
(5, 13, 16, 19, 21, 40)
(5, 13, 16, 19, 24, 35)
(5, 13, 16, 19, 28, 30)
(5, 13, 16, 20, 21, 38)
(5, 13, 19, 20, 21, 32)
(5, 13, 19, 20, 24, 28)
(5, 14, 15, 16, 26, 38)
(5, 14, 15, 19, 26, 32)
(5, 14, 16, 19, 20, 39)
(5, 14, 16, 19, 26, 30)
(5, 14, 19, 20, 24, 26)
(5, 15, 16, 19, 26, 28)
(5, 16, 19, 20, 21, 26)
(6, 7, 10, 26, 38, 40)
(6, 7, 13, 20, 38, 40)
(6, 7, 13, 25, 32, 38)
(6, 7, 16, 25, 26, 38)
(6, 7, 19, 20, 26, 40)
(6, 7, 19, 25, 26, 32)
(6, 8, 10, 26, 35, 38)
(6, 8, 13, 19, 35, 40)
(6, 8, 13, 20, 35, 38)
(6, 8, 13, 25, 28, 38)
(6, 8, 14, 25, 26, 38)
(6, 8, 19, 20, 26, 35)
(6, 8, 19, 25, 26, 28)
(6, 10, 13, 14, 38, 40)
(6, 10, 13, 16, 35, 38)
(6, 10, 13, 19, 28, 40)
(6, 10, 13, 19, 32, 35)
(6, 10, 13, 20, 28, 38)
(6, 10, 14, 19, 26, 40)
(6, 10, 14, 20, 26, 38)
(6, 10, 16, 19, 26, 35)
(6, 10, 19, 20, 26, 28)
(6, 13, 14, 16, 25, 38)
(6, 13, 14, 19, 20, 40)
(6, 13, 14, 19, 25, 32)
(6, 13, 16, 19, 20, 35)
(6, 13, 16, 19, 25, 28)
(6, 14, 16, 19, 25, 26)
(7, 8, 10, 19, 39, 40)
(7, 8, 10, 20, 38, 39)
(7, 8, 10, 26, 30, 38)
(7, 8, 12, 25, 26, 38)
(7, 8, 13, 15, 38, 40)
(7, 8, 13, 19, 25, 48)
(7, 8, 13, 19, 30, 40)
(7, 8, 13, 20, 30, 38)
(7, 8, 13, 24, 25, 38)
(7, 8, 15, 19, 26, 40)
(7, 8, 15, 20, 26, 38)
(7, 8, 16, 19, 25, 39)
(7, 8, 19, 20, 26, 30)
(7, 8, 19, 24, 25, 26)
(7, 10, 12, 13, 38, 40)
(7, 10, 12, 19, 26, 40)
(7, 10, 12, 20, 26, 38)
(7, 10, 13, 15, 32, 38)
(7, 10, 13, 16, 30, 38)
(7, 10, 13, 19, 20, 48)
(7, 10, 13, 19, 24, 40)
(7, 10, 13, 19, 30, 32)
(7, 10, 13, 20, 24, 38)
(7, 10, 15, 16, 26, 38)
(7, 10, 15, 19, 26, 32)
(7, 10, 16, 19, 20, 39)
(7, 10, 16, 19, 26, 30)
(7, 10, 19, 20, 24, 26)
(7, 12, 13, 16, 25, 38)
(7, 12, 13, 19, 20, 40)
(7, 12, 13, 19, 25, 32)
(7, 12, 16, 19, 25, 26)
(7, 13, 15, 16, 19, 40)
(7, 13, 15, 16, 20, 38)
(7, 13, 15, 19, 20, 32)
(7, 13, 16, 19, 20, 30)
(7, 13, 16, 19, 24, 25)
(7, 15, 16, 19, 20, 26)
(8, 10, 12, 13, 35, 38)
(8, 10, 12, 19, 26, 35)
(8, 10, 13, 14, 30, 38)
(8, 10, 13, 15, 28, 38)
(8, 10, 13, 19, 20, 42)
(8, 10, 13, 19, 21, 40)
(8, 10, 13, 19, 24, 35)
(8, 10, 13, 19, 28, 30)
(8, 10, 13, 20, 21, 38)
(8, 10, 14, 15, 26, 38)
(8, 10, 14, 19, 20, 39)
(8, 10, 14, 19, 26, 30)
(8, 10, 15, 19, 26, 28)
(8, 10, 19, 20, 21, 26)
(8, 12, 13, 14, 25, 38)
(8, 12, 13, 19, 20, 35)
(8, 12, 13, 19, 25, 28)
(8, 12, 14, 19, 25, 26)
(8, 13, 14, 15, 19, 40)
(8, 13, 14, 15, 20, 38)
(8, 13, 14, 19, 20, 30)
(8, 13, 14, 19, 24, 25)
(8, 13, 15, 16, 19, 35)
(8, 13, 15, 19, 20, 28)
(8, 13, 16, 19, 21, 25)
(8, 14, 15, 19, 20, 26)
(10, 12, 13, 14, 19, 40)
(10, 12, 13, 14, 20, 38)
(10, 12, 13, 16, 19, 35)
(10, 12, 13, 19, 20, 28)
(10, 12, 14, 19, 20, 26)
(10, 13, 14, 15, 16, 38)
(10, 13, 14, 15, 19, 32)
(10, 13, 14, 16, 19, 30)
(10, 13, 14, 19, 20, 24)
(10, 13, 15, 16, 19, 28)
(10, 13, 16, 19, 20, 21)
(10, 14, 15, 16, 19, 26)
(12, 13, 14, 16, 19, 25)
(13, 14, 15, 16, 19, 20)

    This runs quite fast.