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)
```

Question

- 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?