Super greedy algorithm for Exact Three Cover

Question

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)

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?

• The T: 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.
• Zchpyvr: 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.
• The T: @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.

Answer 1

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]

In-place addition

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

?

• Ben A: 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()))