In my version of the Partition Problem, I have a set of weights that are all powers of three (1, 3, 9, 27 etc.). I only have one of each weight. There is some object (the weight of this object is input) on the left side of a scale and I need to add weights to either side to balance it. I can choose not to use a weight if I so choose (denoted by a '-').
Right now, my program converts the inputted weight into ternary and, if all the digits are 1's and 0's, just feeds in the appropriate factor of three into a list. Otherwise, it generates every possibility, iterating through them until both sides are equal. This is, predictably, very slow. I know the partition problem is NP-C but is there any optimizations I can make here?
import string import pdb import itertools def nearestpowerof3(x): numbers = '012' if x < 0: sign = -1 elif x == 0: return numbers else: sign = 1 x *= sign digits = list() while x: digits.append(numbers[x % 3]) x = int(x / 3) if sign < 0: digits.append('-') digits.reverse() ternary = ''.join(digits) exp = int(len(ternary)) return exp, 3 ** exp, ternary def answer(x): product =  tern = str(nearestpowerof3(x)) print(tern) if tern.find('2') == -1: print('HELLO') for digit in tern[::-1]: if digit == '1': product.append("R") elif digit == '0': product.append("L") return product else: for product in itertools.product('RL-', repeat=len(tern) + 1): left = x right = 0 for i in range(len(product)): if product[i] == 'R': right += 3**i elif product[i] == 'L': left += 3**i if left == right: if product[-1] == '-' and product[-2] != '-': product = product[:-1] return product print(answer(10000000))