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.
This object stores data for a combination option. It has two data members:
value: the value of the option
count: 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
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
options parameter is a list of options,
combine is the function used to combine options,
def getCombinations(options, combine, base): combos = [base] chosen =  * 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
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.