# Super greedy algorithm for Exact Three Cover

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]]): ')

for a in range(0, len(s)):
s[a] = int(s[a])

# Need a prime
# 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

#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

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)


Questions

• 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?
• I just realized a mistake at the end of my code. The reversing will never be executed. So I should place that before the "opps" statements. Jun 28, 2020 at 23:57
• Do you have example input for S and C that could be used to test the script? There are significant improvements that can be made in this script, but I am hesitant to implement them since there is no test case I can use to verify the validity of the code as changes are being made. Jul 1, 2020 at 15:07
• @Zchpyvr I have made my final script here. hackaday.io/project/173227/logs The second one has a large fixed C as shown in link. Jul 16, 2020 at 1:47

## Functions

For many reasons, you should attempt to move your global code into functions. Reasons include testability, meaningful stack traces, and de-cluttering the global namespace.

## User input

This prompt:

input("Input set of integers for S : ")


is missing a description to the user that they should be entering a comma-delimited list.

This input:

input('enter list for C (eg. [[1,2,3],[4,5,6]]): ')


forces the user (who, we should assume, is not a programmer) to both understand and use JSON. JSON is intended as an application-friendly and not user-friendly serialization format. Instead, consider "assisting" the user by looping through and accepting multiple comma-separated (for consistency) lists. Given your example, a loop would execute twice and each iteration would produce a list of three items.

## Iteration

for a in range(0, len(s)):
s[a] = int(s[a])


can be

s = [int(a) for a in s]


count = count + 1


can be

count += 1


## Boolean comparison

if sympy.isprime(count) == True:


should be

if sympy.isprime(count):


## Iteration of a counted variable

count = len(s)//3
while True:
count = count + 1


should be

for count in itertools.count(len(s)//3):


## Wrapping

This is a minor thing, but the comments starting at

# This is a SUPER Greedy


are wrapped to a very small column count. Typically, the smallest column wrap you'll find in the wild is 80. It's probably a good idea to reformat this so that each line goes up to 80 characters long.

## Temporary variables

Consider

n = len(s)


to simplify expressions like

len(s)*241*((len(s)*241)-1)*((len(s)*241)-2)//6


## More iteration

delete = []
for a in range(0, len(c)):
for i in permutations(c[a], 3):


should be

for a in c:
for i in permutations(a, 3):
# ...


## Variable naming

opps = 0


?

• Could be worth mentioning that you can map to an input when splitting it, so you can do it in one line instead of two. s = list(map(int, input(...).split())) Jul 10, 2020 at 20:36