Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import json
- from copy import deepcopy
- import random
- s = input("Input list of integers (no repeating elements) for S with commas (eg. 1,2,3,4...) : ").split(',')
- c = input('enter list for C (eg. [[1,2,3],[4,5,6]]): ')
- c = json.loads(c)
- s = [int(a) for a in s]
- random.seed()
- miss = []
- delete = []
- remove = []
- remove_t=[]
- no = 0
- def input_validation():
- # checking for missing elements.
- no = 0
- for a in range(0, len(c)):
- for b in range(0, len(c[a])):
- miss.append(c[a][b])
- for d in s:
- if d not in miss:
- print('False', d)
- no = 1
- break
- if no == 1:
- quit()
- # Throw out unwanted orderings of sub-lists
- for a in range(0, len(c)):
- c[a] = sorted(c[a])
- # Lists are treated as sets, so lists
- # with repeating elements is thrown out
- for rem in range(0, len(c)):
- if len(c[rem]) != len(set(c[rem])):
- remove.append(c[rem])
- for rem_two in range(0, len(remove)):
- if remove[rem_two] in c:
- del c[c.index(remove[rem_two])]
- # Throw out lists that have elements that do
- # not exist in s.
- for j in range(0, len(c)):
- for jj in range(0, len(c[j])):
- if any(elem not in s for elem in c[j]):
- remove_t.append(c[j])
- for rem_two in range(0, len(remove_t)):
- if remove_t[rem_two] in c:
- del c[c.index(remove_t[rem_two])]
- # remove repeating lists
- s_copy = deepcopy(s)
- input_validation()
- c = [c[x] for x in range(len(c)) if not(c[x] in c[:x])]
- c_copy = deepcopy(c)
- def bijective_mapp():
- s_copy = deepcopy(s)
- for a in range(0, len(s)):
- s[a] = a+1
- for b in range(0, len(c)):
- for bb in range(0, len(c[b])):
- c[b][bb] = s_copy.index(c[b][bb])+1
- bijective_mapp()
- c = [sorted(y) for y in c]
- def shuff(c, n):
- for i in range(n-1,0,-1):
- j = random.randint(0,i)
- c[i],c[j] = c[j],c[i]
- c.append(sorted(c[len(c)-1]))
- n = len(s)
- # Personally, I like to experiment with Prime Constants
- # 1 is the default constant
- steps = n*(2**17)*((n*(2**17))-1)*((n*(2**17))-2)//6
- reset = 0
- c_elem = set()
- set_cover = []
- partial = []
- for a in range(0, steps + 1):
- reset = reset + 1
- if reset > len(c):
- c_elem = set()
- reset = 0
- c = sorted(c, key=lambda parameter: parameter[0])
- shuff(c, len(c))
- set_cover = []
- c.append(c[0])
- del(c[0])
- for l in c:
- if not any(v in c_elem for v in l):
- set_cover.append(l)
- c_elem.update(l)
- # if exact solution not found,
- # then use partial solution
- if set_cover not in partial:
- partial.append(set_cover)
- list_of_partials = [len(r) for r in partial]
- # Get the largest Set_Cover Found
- k = partial[list_of_partials.index(max(list_of_partials))]
- # Reversing the Bijective mapping
- # to the original input. But, its sorted.
- for a in range(0, len(k)):
- for b in range(0, len(k[a])):
- l = s.index(k[a][b])
- k[a][b] = s_copy[l]
- # Returns false if no solution exists
- # or if it failed to find one.
- print(len(k)==len(s)//3, k)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement