Advertisement
Guest User

Subset Product Heuristic (fixed typo that confused l & 1)

a guest
Nov 13th, 2020
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.57 KB | None | 0 0
  1. import random
  2. import json
  3. from operator import mul
  4. from functools import reduce
  5.  
  6.  
  7. c = 1, 2, 4, 7, 8, 14, 28, 56, 5507, 11014, 22028, 38549, 44056, 77098, 154196, 308392, 140186621, 280373242, 560746484, 981306347, 1121492968, 1962612694, 3925225388, 7850450776, 772007721847, 1544015443694, 3088030887388, 5404054052929, 6176061774776, 10808108105858, 21616216211716
  8. N = reduce(mul, c[15:28])
  9.  
  10. # REMOVE REPEATING INTEGERS
  11. c = [c[x] for x in range(len(c)) if not(c[x] in c[:x])]
  12. c = sorted(c)
  13. reset = 0
  14. subset_prod = []
  15. covered_elements = []
  16.  
  17. # shuffling list function
  18. def shuff(c, n):
  19.     for i in range(n-1,0,-1):
  20.         j = random.randint(0,i)
  21.         c[i],c[j] = c[j],c[i]
  22.  
  23. c.append(c[len(c)-1])
  24. random.seed()
  25. shuff(c, len(c))
  26. n = len(c)
  27. b = 10
  28. steps = n*(2**b)*((n*(2**b))-1)*((n*(2**b))-2)//6
  29.  
  30. # Fixed semantic bug that
  31. # cleared lists prematurely.
  32. for a in range(1, steps + 1):
  33.     reset = reset + 1
  34.     if reset > len(c):
  35.         covered_elements = []
  36.         reset = 0
  37.         shuff(c, len(c))
  38.     c.append(c[0])
  39.     del [c[0]]
  40.     for l in c:
  41.         if l not in covered_elements:
  42.             if N % l == 0:
  43.                 if len(covered_elements) == 0:
  44.                     covered_elements.append(l)
  45.                 if len(covered_elements) > 0:
  46.                     if l not in covered_elements:
  47.                         if reduce(mul, covered_elements) < N:
  48.                             covered_elements.append(l)
  49.     if reduce(mul,covered_elements) == N:
  50.         print('Found Subset Product', covered_elements)
  51.         break
  52.         break
  53.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement