Advertisement
Guest User

Subset Product

a guest
Nov 12th, 2020
632
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.04 KB | None | 0 0
  1. import random
  2. import json
  3. from operator import mul
  4. from functools import reduce
  5.  
  6. # Given a target input of N.
  7. # find a subset-product from c.
  8.  
  9. N = 16759893777012736
  10. 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
  11.  
  12. # REMOVE REPEATING INTEGERS
  13. c = [c[x] for x in range(len(c)) if not(c[x] in c[:x])]
  14. c = sorted(c)
  15. stop = 0
  16. reset = 0
  17. subset_prod = []
  18.  
  19. # shuffling list functioon
  20. def shuff(c, n):
  21.     for i in range(n-1,0,-1):
  22.         j = random.randint(0,i)
  23.         c[i],c[j] = c[j],c[i]
  24.  
  25. c.append(c[len(c)-1])
  26. random.seed()
  27. shuff(c, len(c))
  28. n = len(c)
  29. # 10 is the constant I randomly picked.
  30. # you can choose whatever you want.
  31. b = 10
  32. steps = n*(2**b)*((n*(2**b))-1)*((n*(2**b))-2)//6
  33.  
  34. while stop <= steps:
  35.  
  36.     reset = reset + 1
  37.     stop = stop + 1
  38.  
  39.     # resets all variables
  40.     # because of the possibility
  41.     # of missing a needed integer
  42.    
  43.     if reset > len(c):
  44.         covered_elements = []
  45.         reset = 0
  46.         shuff(c, len(c))
  47.            
  48.     # Keep c[0]
  49.     # and append to
  50.     # end of list
  51.     # del c[0]
  52.     # to push >>
  53.     # in list.
  54.    
  55.     c.append(c[0])
  56.     del [c[0]]
  57.     covered_elements = []
  58.  
  59.    
  60.     for l in c:
  61.         if l not in covered_elements:
  62.             if N % l == 0:
  63.                 if len(covered_elements) == 0:
  64.                     covered_elements.append(l)
  65.                 if len(covered_elements) > 0:
  66.                     if l not in covered_elements:
  67.                         if reduce(mul, covered_elements) < N:
  68.                             covered_elements.append(l)
  69.  
  70.                    
  71.  
  72.  
  73.     if reduce(mul,covered_elements) not in subset_prod:
  74.         subset_prod.append(reduce(mul,covered_elements))
  75.  
  76.     if N in subset_prod:
  77.         print('Found Subset Product',covered_elements)
  78.         break
  79.         break
  80.  
  81.  
  82.  
  83.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement