4
\$\begingroup\$

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))
\$\endgroup\$
4
\$\begingroup\$

I don't see a partition problem here. What the task suggests is a representation of a given number in the form of \$\Sigma a_n3^n\$ where \$a_n \in \{-1,0,1\}\$. I highly recommend proving to (or at least convincing) yourself that every number has such representation. Then you may want to see how few first numbers are represented:

    1                   1
    2                  -1  1
    3                   0  1
    4                   1  1
    5                  -1 -1  1
    6                   0 -1  1
    7                   1 -1  1
    8                  -1  0  1
    9                   0  0  1
    10                  1  0  1
    11                 -1  1  1
    12                  0  1  1
    13                  1  1  1
    14                 -1 -1 -1  1

(first column is for 1, second for 3, third for 9, etc) and figure out the rule of sequencing the coefficients for each power of 3 (think reminders). The actual coding becomes straightforward.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.