Let's say we have numbers factors, for example 1260: >>> factors(1260) [2, 2, 3, 3, 5, 7] Which would be best way to do in Python combinations with every subproduct possible from these numbers, ie all factorings, not only prime factoring, with sum of factors less than max_product? If I do combinations from the prime factors, I have to refactor remaining part of the product as I do not know the remaining part not in combination. I can also refine my divisors function to produce pairs of divisors instead of divisors in size order, but still it will cost me to do this for number with product upto 12000. The product must remain always the same. I was linked to divisor routine, but it did not look worth the effort to prove them to adopt to my other code. At least my divisor function is noticably faster than sympy one: def divides(number): if number<2: yield number return high = [number] sqr = int(number ** 0.5) limit = sqr+(sqr*sqr != number) yield 1 for divisor in xrange(3, limit, 2) if (number & 1) else xrange(2, limit): if not number % divisor: yield divisor high.append(number//divisor) if sqr*sqr== number: yield sqr for divisor in reversed(high): yield divisor Only problem to reuse this code is to link the divisors to factoring sieve or do some kind of itertools.product of divisors of the divisors in pairs, which I would give out as pairs instead of sorting to order. Example results would be: [4, 3, 3, 5, 7] (one replacement of two) [5, 7, 36] (one replacement of three) [3, 6, 14, 5] (two replacements) Probably I would need some way to produce sieve or dynamic programming solutions for smaller divisors which could be linked to numbers whose divisors they are. Looks difficult to avoid overlap though. I do have one sieve function ready which stores biggest prime factor for each number for speeding up the factoring without saving complete factorings of every number... maybe it could be adapted. UPDATE: The sum of factors should be near the product, so probably there is high number of factors of <= 10 in answer (upto 14 factors). UPDATE2: Here is my code, but must figure out how to do multiple removals recursively or iteratively for parts > 2 long and dig up the lexical partitioning to replace the jumping bit patterns which produce duplicates (pathetic hit count only for one replacement, and that does not count the passing of 'single element partionings' inside the single_partition): from __future__ import print_function import itertools import operator from euler import factors def subset(seq, mask): """ binary mask of len(seq) bits, return generator for the sequence """ # this is not lexical order, replace with lexical order masked passing duplicates return (c for ind,c in enumerate(seq) if mask & (1<<ind)) def single_partition(seq, n = 0, func = lambda x: x): ''' map given function to one partition ''' for n in range(n, (2**len(seq))): result = tuple(subset(seq,n)) others = tuple(subset(seq,~n)) if len(result) < 2 or len(others) == 0: #empty subset or only one or all continue result = (func(result),)+others yield result if __name__=='__main__': seen, hits, count = set(), 0, 0 for f in single_partition(factors(13824), func = lambda x: reduce(operator.mul, x)): if f not in seen: print(f,end=' ') seen.add(f) else: hits += 1 count += 1 print('\nGenerated %i, hits %i' %(count,hits)) REFINEMENT I am happy to get only the factorings with max 5 factors in the non-prime factor parts. I have found by hand that non-decreasing arrangements for up to 5 same factors follow this form: partitions of 5 applied to 2**5 1 1 1 1 1 2 2 2 2 2 1 1 1 2 2 2 2 4 1 1 1 3 2 2 8 1 2 2 2 4 4 1 4 2 16 2 3 4 8 Continue reading...
