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')
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?