I developed the following Python functions when solving a few Project Euler problems, and since I'm not that familiar with Python, I'm curious at how I could improve them.
The code consists of a data holder class, and a few functions.
Option class:
This object stores data for a combination option. It has two data members:
value
: the value of the optioncount
: how many times this option can be chosen
class Option:
def __init__(self, value, count):
self.value = value
self.count = count
Get Prime Factorization:
This function calculates a number's prime factorization. It returns the factorization as a list of Options where the option's value
is the prime and it's count
is the power.
def getPrimeFactorization(n):
f = []
nth = 0
while n > 1:
prime = nthPrime(nth)
if n % prime == 0:
f.append(Option(prime, 1))
n = n // prime
while n % prime == 0:
f[-1].count += 1
n = n // prime
nth += 1
return f
Get Combinations:
To calculate the combinations, I use getCombinationsIncrement
to iterate through each possible combination. The index
is the index of the current option, options
is the list of Options, and chosen
is the number of times the Option will be chosen.
def getCombinationsIncrement(index, options, chosen):
if index >= len(options):
return False
else:
chosen[index] += 1
if chosen[index] > options[index].count:
chosen[index] = 0
return getCombinationsIncrement(index + 1, options, chosen)
else:
return True
The options
parameter is a list of options, combine
is the function used to combine options, base
is the base amount to combine with other values (it's similar to reduce if your familiar with JavaScript).
def getCombinations(options, combine, base):
combos = [base]
chosen = [0] * len(options)
while getCombinationsIncrement(0, options, chosen):
combos.append(base)
for i in range(len(options)):
for _ in range(chosen[i]):
combos[-1] = combine(combos[-1], options[i].value)
combos.sort()
return combos
Get Divisors
Using the functions above it's easy to calculate all the divisors of a number.
def multiply(x, y):
return x * y
def getDivisors(n):
return getCombinations(getPrimeFactorization(n), multiply, 1)
My primary concern is with the getCombinationsIncrement
function. I'd like it to be scoped only into the getCombinations
function, and I don't particularly like having to make a class to fix that. It also might not be the best way to go about creating the combinations.