Advertisement
Guest User

Solving Subset Product

a guest
Apr 23rd, 2022
542
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.96 KB | None | 0 0
  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
Add Comment
Please, Sign In to add comment
Advertisement