Advertisement
Guest User

Three Cover "Approximation"

a guest
Dec 31st, 2020
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.15 KB | None | 0 0
  1. import json
  2. from copy import deepcopy
  3. import random
  4.  
  5. s =  input("Input list of integers (no repeating elements) for S with commas (eg. 1,2,3,4...) : ").split(',')
  6. c =  input('enter list for C (eg. [[1,2,3],[4,5,6]]): ')
  7. c = json.loads(c)
  8. s = [int(a) for a in s]
  9.  
  10. random.seed()
  11. miss = []
  12. delete = []
  13. remove = []
  14. remove_t=[]
  15. no = 0
  16. def input_validation():
  17.     # checking for missing elements.
  18.     no = 0
  19.     for a in range(0, len(c)):
  20.         for b in range(0, len(c[a])):
  21.             miss.append(c[a][b])
  22.     for d in s:
  23.         if d not in miss:
  24.             print('False', d)
  25.             no = 1
  26.             break
  27.     if no == 1:
  28.         quit()
  29.     # Throw out unwanted orderings of sub-lists
  30.     for a in range(0, len(c)):
  31.         c[a] = sorted(c[a])
  32.     # Lists are treated as sets, so lists
  33.     # with repeating elements is thrown out        
  34.     for rem in range(0, len(c)):
  35.         if len(c[rem]) != len(set(c[rem])):
  36.             remove.append(c[rem])
  37.     for rem_two in range(0, len(remove)):
  38.         if remove[rem_two] in c:
  39.             del c[c.index(remove[rem_two])]
  40.     # Throw out lists that have elements that do
  41.     # not exist in s.
  42.     for j in range(0, len(c)):
  43.         for jj in range(0, len(c[j])):
  44.             if any(elem not in s for elem in c[j]):
  45.                 remove_t.append(c[j])
  46.     for rem_two in range(0, len(remove_t)):
  47.         if remove_t[rem_two] in c:
  48.             del c[c.index(remove_t[rem_two])]
  49.        
  50. # remove repeating lists
  51. s_copy = deepcopy(s)
  52. input_validation()
  53. c = [c[x] for x in range(len(c)) if not(c[x] in c[:x])]
  54. c_copy = deepcopy(c)
  55. def bijective_mapp():
  56.     s_copy = deepcopy(s)
  57.     for a in range(0, len(s)):
  58.         s[a] = a+1
  59.     for b in range(0, len(c)):
  60.         for bb in range(0, len(c[b])):
  61.             c[b][bb] = s_copy.index(c[b][bb])+1
  62. bijective_mapp()
  63. c = [sorted(y) for y in c]
  64. def shuff(c, n):
  65.     for i in range(n-1,0,-1):
  66.         j = random.randint(0,i)
  67.         c[i],c[j] = c[j],c[i]
  68. c.append(sorted(c[len(c)-1]))
  69. n = len(s)
  70. # Personally, I like to experiment with Prime Constants
  71. # 1 is the default constant
  72. steps = n*(2**17)*((n*(2**17))-1)*((n*(2**17))-2)//6
  73. reset = 0
  74. c_elem = set()
  75. set_cover = []
  76. partial = []
  77. for a in range(0, steps + 1):
  78.     reset = reset + 1
  79.     if reset > len(c):
  80.         c_elem = set()
  81.         reset = 0
  82.         c = sorted(c, key=lambda parameter: parameter[0])
  83.         shuff(c, len(c))
  84.         set_cover = []
  85.     c.append(c[0])
  86.     del(c[0])
  87.     for l in c:
  88.         if not any(v in c_elem for v in l):
  89.             set_cover.append(l)
  90.             c_elem.update(l)
  91.     # if exact solution not found,
  92.     # then use partial solution
  93.     if set_cover not in partial:
  94.         partial.append(set_cover)
  95.     list_of_partials = [len(r) for r in partial]
  96. # Get the largest Set_Cover Found
  97. k = partial[list_of_partials.index(max(list_of_partials))]
  98. # Reversing the Bijective mapping
  99. # to the original input. But, its sorted.
  100. for a in range(0, len(k)):
  101.     for b in range(0, len(k[a])):
  102.         l = s.index(k[a][b])
  103.         k[a][b] = s_copy[l]
  104. # Returns false if no solution exists
  105. # or if it failed to find one.
  106. print(len(k)==len(s)//3, k)
  107.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement