I had trouble solving instances of Exact Three Cover with 100 units in input C. All in a reasonable amount of time. Mainly because the problem is NP-complete. So I came up with an approximate solution (Don’t ask me the ratio for correctness, because I don’t know) I have gotten 100, 500 and 1000 units in C to return correct solutions. Screenshot of 3000 units in C. And, here is a link to my approximation algorithm where C has 100 units.
I believe that if I don’t have significant amounts of chaff (sets that could cause my algorithm to fail) I can solve instances of Exact Three Cover I usually come upon quite quickly.
Now, I don’t have to wait for millennia to solve C with 500 units when I encounter these cases.
Please don’t ask me to change my constants; because I’m testing for 10,000 units in C. So I need a large constant for my while-loop.
import random from itertools import combinations from itertools import permutations import sympy import json s = input("Input set of integers for S : ").split(',') c = input('enter list for C (eg. ((1,2,3),(4,5,6))): ') c = json.loads(c) for a in range(0, len(s)): s(a) = int(s(a)) # Need a prime # seems to help spread # 3sets apart. count = len(s)//3 while True: count = count + 1 if sympy.isprime(count) == True: prime = count break # This is a SUPER Greedy # Algorithim that runs # in polynomial time. # It is impractical # for NO instances # It will TAKE FOREVER (constant of 241.. Duhh...) # to halt and # return an approximated # no. # The purpose of why I got # such a large constant # is because I needed # to find Exact Three # Covers in lists of C with # lengths of 100, 500, 1000 # units long. # The Exact 2^n solution # is unreasonably to long # for me. # This is a formula # to count all # possible combinations # of THREE except # I am using a constant # value of 241. while_loop_steps = len(s)*241*((len(s)*241)-1)*((len(s)*241)-2)//6 # Don't worry about this. #p = (len(s)//3)/while_loop_steps * 100 if len(s) % 3 != 0: print('invalid input') quit() # Sort list to remove # sets like (1,2,3) and (1,3,2) # but leave (1,2,3) delete = () for a in range(0, len(c)): for i in permutations(c(a), 3): if list(i) in c(a:): if list(i) != c(a): delete.append(list(i)) for a in range(0, len(delete)): if delete(a) in c: del c(c.index(delete(a))) # remove sets # that have # repeating # elements remove = () 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))) # remove sets # that have # elements # that don't # exist in S. remove=() 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.append(c(j)) for rem_two in range(0, len(remove)): if remove(rem_two) in c: del c(c.index(remove(rem_two))) # Remove repeating sets solutions =(c(x) for x in range(len(c)) if not(c(x) in c(:x))) # check left and right for solutions def check_for_exact_cover(jj): jj_flat = (item for sub in jj for item in sub) jj_set = set(jj_flat) if set(s) == jj_set and len(jj_set) == len(jj_flat): print('yes', jj) quit() # Well if length(c) is small # use brute force with polynomial constant if len(c) <= len(s)//3*2: for jj in combinations(c, len(s)//3): check_for_exact_cover(jj) if len(c) >= len(s)//3*2: for jj in combinations(c(0:len(s)//3*2), len(s)//3): check_for_exact_cover(jj) if len(c) >= len(s)//3*2: X = list(reversed(c)) for jj in combinations(X(0:len(s)//3*2), len(s)//3): check_for_exact_cover(jj) # Well, I have to quit # if the loop above # didn't find anything. # when len(c) <= len(s)//3*2 if len(c) <= len(s)//3*2: quit() # will need these Three (what a prime!) # just in case my algorithim # needs to reverse in loop. length = len(solutions) ss = s c = solutions # Primes # have been # observed # in nature # to help # avoid conflict. # So why not # pre shuffle C # prime times? for a in range(0, prime): random.shuffle(c) # while loop to see # if we can find # an Exact Three Cover # in poly-time. stop = 0 Potential_solution = () opps = 0 failed_sets = 0 #Don't worry about this. (100/p*while_loop_steps) while stop <= while_loop_steps: # Shuffling c randomly # this seems to help # select a correct set opps = opps + 1 stop = stop + 1 random.shuffle(c) if len(Potential_solution) == len(ss) // 3: # break if Exact # three cover is # found. print('YES SOLUTION FOUND!',Potential_solution) print('took',stop,'steps in while loop') failed_sets = failed_sets + 1 break # opps helps # me see # if I miss a correct # set if opps > len(c): if failed_sets < 1: s = set() opps = 0 # Keep c(0) # and append to # end of list # del c(0) # to push >> # in list. c.append(c(0)) del (c(0)) Potential_solution = () s = set() for l in c: if not any(v in s for v in l): Potential_solution.append(l) s.update(l) if len(Potential_solution) != len(ss)//3: if stop == length: # Reverse list just # to see if I missed a solution for cc in range(0, len(c)): c = list(reversed(c)) random.shuffle(c)
- What parts of my sorting algorithms could be shortened and improved?
- Is the usage of primes to theoretically space out sets pointless?
- What variable names would you use in my code?