Subset Product Algorithm

Question

Subset Product is an NP-complete problem and is my favorite problem. So, I've written a slightly smarter way of solving the problem.

Will performance impact matter if I use multi-cpus and my GPU?
Do my variable names make sense of what I'm doing?
Is there a better way to write the for-loop under the variable "max_combo"?

The Python Script

import itertools
from itertools import combinations
from functools import reduce
from operator import mul
from sys import exit
# Give TARGET whole number > 0 and give whole number divisors > 0 for D 
# and see if a combination will have a total product equal to TARGET.
TARGET = int(input('enter target product: ' ))
D = input('Enter numbers: ').split(',')
D = list(set([int(a) for a in D]))
# Only divisors are allowed and must be sorted in ascending order for the algorithm to 
# properly work.
D = sorted([i for i in D if TARGET % i==0])
# Using two-sum solution for two-product
two_prod_dict = {}
for a in range(0, len(D)):
    if TARGET//int(D[a]) in two_prod_dict:
        print('YES')
        exit(0)
    else:
       two_prod_dict[int(D[a])] = a

if TARGET in D:
    print('YES')
    exit(0)
# A combination's total product cannot be larger
# than the TARGET. So this code section figures out
# the biggest combination size. (Doing my best to save running time)
max_combo = []
for a in D:
    max_combo.append(a)
    if reduce(mul,max_combo) >= TARGET:
        if reduce(mul,max_combo) > TARGET:
            max_combo.pop()
            break
        else:
            break

This is the purpose of max_combo and in this case len(max_combo) = 5. Suppose TARGET = 120. Some of the divisors for D is 1,2,3,4,5,6,8,10,12. Notice that 5! = 120. (eg. (1,2,3,4,5) = TARGET) So, if you get a combination with six or more numbers it will go over because 6! > TARGET. Remember D is sorted in ascending order for the concept to work and it has no repeating numbers.

# Using any other divisor will go over TARGET.
# To save running time, do it only one time. 
# Taking (1,2,3,4,6) will go over so stop at (1,2,3,4,5) (if there is one). 
# So why waste running time?

for X in combinations(D, len(max_combo)):
    if reduce(mul, X) == TARGET:
        print('YES')
        exit(0)
    else:
        break
# I'm hoping that smaller solutions
# are more likely than larger solutions so start
# with the smallest and work your way up.
for A in range(3, len(max_combo) + 1):
    for X in combinations(D, A):
        if reduce(mul, X) == TARGET:
            print('YES',X)
            exit(0)
print('NO')

You've asked some good algorithmic questions on CodeReview, which is great. But contrary to multiple suggestions, you still aren't putting your code in functions. By doing that you are ignoring the most important advice you've received here. I don't say this in a mean-spirited way, but I am trying to get your attention. The biggest improvement you can make is to embrace functions. — FMc
– FMc, Commented Apr 24, 2022 at 17:48
@FMc Yes, functions they help chunk things out. But I didn't see how I can use them here. — The T
– The T, Commented Apr 24, 2022 at 19:45
You can at least put the whole "algorithmic part" in a function, separating it from the code that prints the result — user555045
– user555045, Commented Apr 24, 2022 at 19:48
@harold Perhaps, I can take the last two for loops and create a function that will do the same. — The T
– The T, Commented Apr 24, 2022 at 19:53
(1) You have experts telling you to put code in functions. One sensible approach is to mimic the experts even if you don't fully appreciate why yet. (2) Here's one specific reason: code inside a function can be tested easily and even in an automatic fashion. Code outside of functions is more of a hassle to test, usually involving manual edits, and that hassle tends to discourage adequate testing. Here's a recent example with some general relevance to your situation. — FMc
– FMc, Commented Apr 24, 2022 at 20:09

greybeard · Accepted Answer · 2022-04-25 09:18:07Z

Reasons to put code in functions (and classes):

Code on module level is evaluated right away:
I can't try it out using copy&paste if there is an input() somewhere.
you don't need to import sys.exit()

Code in a function is documented:

def subset_product(target, factors):
    """ For a natural number target and an iterable of natural number factors, 
        return target equals the product of some of the factors, all or none.
    """
    pass  # that's how many a function starts out

if __name__ == '__main__':
    help(subset_product)

Do my variable names make sense?

There are conventions, not following them for no obvious reason is a distraction or harms readability.
target would have been impeccable.
Single letter names are useful to indicate a name intended be used in its (very) restricted context, only - iteration variables get single letter names quite often (even _ if the value will not be used).

You comment your code: Great, this enables others as well as your later self to get what you've been up to.
Caveat: Keep comments up to date.

[What is a decent way to code computing an upper limit on the number of factors]?

def subset_product(target, factors):
    """ For a natural number target and an iterable of natural numbered factors, 
        return target equals the product of some of the factors, all or none.
        A factor may be given more than once.
    """
    if target == 1:
        return True
    factors = (int(f) for f in factors)
    divisors = sorted(d for d in factors if 1 < d and target % d == 0)
    if not divisors:
        return False
    if divisors[-1] == target:
        return True
    
    product = 1
    for i, d in enumerate(divisors):
        product *= d
        if target <= product:
            break
    if target == product:
        return True
    max_factors = i
    …

I don't get the idea for "the for X in combinations(D, len(max_combo)) loop" -
immediately following it you express hope that smaller solutions are more likely and act the type.

allowing target and factors below 1 sure complicates things:

def subset_product(target, factors):
    """ For a whole number target and an iterable of whole factors, 
        return target equals the product of some of the factors, all or none.
        A factor may be given more than once.
    """
    special_case = special_subset_product(target, factors)  # 1: True 0: 0 in factors
    if special_case is not None:  # target in factors, too?
        return special_case
    sign = -1 if target < 0 else 1
    target *= sign
    factors = (int(f) * sign for f in factors)
    divisors = sorted(d for d in factors if d != 0 and d != 1 and target % d == 0)
    if not divisors:
        return False
    if divisors[-1] == target:
        return True
    # now *what*?

Stack Exchange Network

Subset Product Algorithm

1 Answer 1

You must log in to answer this question.

Linked

Hot Network Questions

Subset Product Algorithm

1 Answer 1

You must log in to answer this question.

Linked

Related

Hot Network Questions