Advertisement
Guest User

Solving Subset Product

a guest
Apr 23rd, 2022
76
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import itertools
  2. from itertools import combinations
  3. from functools import reduce
  4. from operator import mul
  5. from sys import exit
  6. # Given a whole number > 0 for TARGET, and a set of whole numbers > 0 that are divisors of TARGET. Is there a combination of divisors in SET that have a total product equivalent to TARGET?
  7. TARGET = int(input('enter target product: ' ))
  8. SET = input('Enter numbers: ').split(',')
  9. SET = list(set([int(a) for a in SET]))
  10. # Using two-sum solution for two-product
  11. two_prod_dict = {}
  12. for a in range(0, len(SET)):
  13.     if TARGET//int(SET[a]) in two_prod_dict:
  14.         print('YES')
  15.         exit(0)
  16.     else:
  17.        two_prod_dict[int(SET[a])] = a
  18. # creating a set of all whole number divisors
  19. divisors = set()
  20. for i in SET:
  21.     if TARGET % i == 0:
  22.         divisors.add(i)
  23. # Divisors are sorted in ascending order.
  24. # so that max_combo can correctly select
  25. # the largest possible combination size.
  26. divisors = sorted(divisors)
  27. if TARGET in divisors:
  28.     print('YES')
  29.     exit(0)
  30. # finds the maximum combination size
  31. # Simply multiplies each I in divisors
  32. # until reaches the closest
  33. # value without going over.
  34. # A combination's total product cannot be larger
  35. # than the TARGET.
  36. max_combo = []
  37. for a in divisors:
  38.     max_combo.append(a)
  39.     if reduce(mul,max_combo) >= TARGET:
  40.         if reduce(mul,max_combo) > TARGET:
  41.             max_combo.pop()
  42.             break
  43.         else:
  44.             break
  45. # Using any other divisor will go over TARGET.
  46. # To save running time, do it only one time.
  47. for X in combinations(divisors, len(max_combo)):
  48.     if reduce(mul, X) == TARGET:
  49.         print('YES')
  50.         exit(0)
  51.     else:
  52.         break
  53. # I'm hoping that smaller solutions
  54. # are more likely than larger solutions so start
  55. # with the smallest and work your way up.
  56. for A in range(3, len(max_combo) + 1):
  57.     for X in combinations(divisors, A):
  58.         if reduce(mul, X) == TARGET:
  59.             print('YES',X)
  60.             exit(0)
  61. print('NO')
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement