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
THE SOLUTION I do not remove the accepted answer from fine solution down, but it is over complicated for the job. From Project Euler I reveal only this helper function from orbifold of NZ, it works faster and without needing the prime factors first:
def factorings(n,k=2):
result = []
while k*k <= n:
if n%k == 0:
result.extend([[k]+f for f in factorings(n/k,k)])
k += 1
return result + [[n]]
The relevant solution for problem 88 of his run in Python 2.7 in 4.85 s by my timing decorator and after optimizing the stop condition by found counter 3.4 s in 2.6.6 with psyco, 3.7 s in 2.7 without psyco . Speed of my own code went from 30 seconds with code in accepted answer (sorting added by me removed) to 2.25 s (2.7 without psyco) and 782 ms with psyco in Python 2.6.6.
I use a list like [(2, 9), (3, 3)] (for [2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3]) as the base list of unexpanded factors and a list of expanded factors. In each round I pick one factor from the base, decreasing it's count, and
With dynamic programming and the cutoff strategy this became extremely fast:
from itertools import groupby
def multiplicies( factors ):
""" [x,x,x,,y,y] -> [(x,3), (y,2)] """
return ((k, sum(1 for _ in group)) for k, group in groupby(factors))
def combinate(facs, cutoff=None):
facs = tuple(multiplicies(facs))
results = set()
def explode(base, expanded):
# `k` is the key for the caching
# if the function got called like this before return instantly
k = (base, expanded)
if k in results:
return
results.add(k)
# pick a factor
for (f,m) in base:
# remove it from the bases
newb = ((g, (n if g!=f else n-1)) for g,n in base)
newb = tuple((g,x) for g,x in newb if x > 0)
# do we cutoff yet?
if cutoff is None or len(newb) + len(expanded) < cutoff:
explode(newb, tuple(sorted(expanded + (f,))))
# multiply the pick with each factor in expanded
for pos in range(len(expanded)):
newexp = list(expanded)
newexp[pos] *= f
explode(newb, tuple(sorted(newexp)))
explode(facs, ())
# turn the `k` (see above) into real factor lists
return set((tuple((x**y) for x,y in bases) + expanded)
for (bases, expanded) in results)
# you dont even need the cutoff here!
combinate([2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3])
# but you need it for
combinate([2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3,5,7,9,11], 5)
Try Psyco if you can (I cant because I only have Py2.7 here), it might speed this up quite a bit too.