Solving Subset-Product in Python

Question

I've written a python script that solves a restricted variant of Subset Product by using integer factorization. The purpose of the script is for my empirical observations of the similarities between factorization and the NP-complete problem.

The code compares two sets (or lists) from the original input arr and the factor list res. Because of the comparison, it is able to find the divisors and multiply them to see if they arrive to the target product.

Before using the code be aware that input must be positive integers only.

print('Solves restricted Subset Product') print('Where only non-repeating integers exist in list') print('Subset Product Solver') arr = list(map(int, input('Enter numbers WITH SPACES: ').split(' '))) print('enter your target integer: ') target = int(input()) # Here I am using the same algorithm # for integer factorization for a # restricted variant of subset product res = []; for i in range(1, target+1): if target % i == 0: res.append(i) compare_sets = set(res) & set(arr) # These lines of code multiply all elements # in compare_sets. def multiplyList(compare_sets) : # Multiply elements one by one result = 1 for x in compare_sets: result = result * x return result # Driver code k = multiplyList(compare_sets) # This loop is intended to comb through the # compare_sets list. To make sure I don't go # over and miss the target integer for i in compare_sets: if k / i == target: if len(compare_sets) > 1: compare_sets.remove(i) print('yes, a subset product exists') print(compare_sets) quit() if k == target: if len(compare_sets) > 1: print('yes, a subset product exists') print(set(res) & set(arr)) quit() else: print('no') quit() print('no') 

Question

Are my variable names funky and should be re-written? What part of the code is the worst in terms of time complexity (ignoring factoring)? What more efficient "pythonic" methods can I use to improve the code?

Answer 1

res = []; for i in range(1, target+1): if target % i == 0: res.append(i) 

This has a couple notable things. First, Python doesn't use semi-colons in the vast majority of cases. They aren't necessary. Also, whenever you have a loop whose only purpose is to create a list, you'll likely want a list comprehension instead:

res = [i for i in range(1, target + 1) if target % i == 0] 

Whatever is on the left end (i in this case) gets appended to a new list. It can also be "guarded" using an if on the right end. Once you get used to seeing this syntax, it tends to read really nicely.

I also wouldn't write target+1 without any spaces. PEP8 recommends one space on each side of a binary operator unless you have a good reason to omit them.

---

result = 1 for x in compare_sets: result = result * x return result 

The line in the loop could make use of a compound-assignment operator to be more terse:

result *= x 

This loop though is just carrying out a transformation of an "accumulator" (result). This is the ideal case for reduce:

from operator import mul from functools import reduce result = reduce(mul, compare_sets) 

reduce is a function from Functional Programming. It and map are the standard ways of working with lists at a low level in FP. Python decided to tuck it away in functools, but it's a very useful function. And mul is just:

def mul(a, b): "Same as a * b." return a * b 

operator contains many similar "first order" versions of operators for cases like this.

---

I wouldn't have top-level code like you do here. If you try to load this file by importing it or opening it in a REPL, the whole thing is forced to run, even if you just wanted to use or test a single function. Everything that isn't a function or constant definition should ideally be tucked away inside a main. That way you can control when the code is executed. I'd also be hesitant to call quit here. That also makes code harder to work with. Again, if you have this open in a REPL, quit will kill the REPL. I'd just change those quits to returns once this is inside a main.

---

And your naming isn't too bad. I would use much more descriptive names than i and k though unless those are straight from the equations involved (and even then description always helps).