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 # and append to # end of list # del c # to push >> # in list. c.append(c) del [c] 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?