Python factorization
algorithm, python
Solution
Well, not only you have 3 loops, but this approach won't work if you have more than 3 factors :)
One possible way:
def genfactors(fdict):
factors = set([1])
for factor, count in fdict.iteritems():
for ignore in range(count):
factors.update([n*factor for n in factors])
# that line could also be:
# factors.update(map(lambda e: e*factor, factors))
return factors
factors = {2:3, 3:2, 5:1}
for factor in genfactors(factors):
print factor
Also, you can avoid duplicating some work in the inner loop: if your working set is (1,3), and want to apply to 2^3 factors, we were doing:
- `(1,3) U (1,3)*2 = (1,2,3,6)`
- `(1,2,3,6) U (1,2,3,6)*2 = (1,2,3,4,6,12)`
- `(1,2,3,4,6,12) U (1,2,3,4,6,12)*2 = (1,2,3,4,6,8,12,24)`
See how many duplicates we have in the second sets?
But we can do instead:
- `(1,3) + (1,3)*2 = (1,2,3,6)`
- `(1,2,3,6) + ((1,3)*2)*2 = (1,2,3,4,6,12)`
- `(1,2,3,4,6,12) + (((1,3)*2)*2)*2 = (1,2,3,4,6,8,12,24)`
The solution looks even nicer without the sets:
def genfactors(fdict):
factors = [1]
for factor, count in fdict.iteritems():
newfactors = factors
for ignore in range(count):
newfactors = map(lambda e: e*factor, newfactors)
factors += newfactors
return factors
Problem
I'd just like to know the best way of listing all integer factors of a number, given a dictionary of its prime factors and their exponents. For example if we have {2:3, 3:2, 5:1} (2^3 * 3^2 * 5 = 360) Then I could write: ``` for i in range(4): for j in range(3): for k in range(1): print 2**i * 3**j * 5**k ``` But here I've got 3 horrible for loops. Is it possible to abstract this into a function given any factorization as a dictionary object argument?