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[0]
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)[2])
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))
