Exact Three Cover.
py  6.70 kB  06/19/2020 at 05:12 

from itertools import groupby
import random
from itertools import combinations
from itertools import permutations
import sympy
s = 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30
c = [[1,2,3],[1,2,4],[1,2,5],[1,2,6],[3,4,5],[3,4,6],[3,4,7],[4,5,6],[4,5,7],[6,3,7],[7,10,11],[22,1,11],[22,27,29],[30,1,14],[30,13,14],[14,20,11],[25,27,29],[14,1,2],[14,2,3],[14,5,1],[26,4,13],[26,7,17],[27,29,18],[19,27,13],[3,4,13],[19,2,1],[19,20,9],[18,3,2],[29,26,1],[5,3,11],[13,16,19],[13,20,21],[13,1,9],[17,19,23],[1,3,5],[5,3,2],[6,8,1],[7,30,23],[11,19,7],[7,4,28],[7,4,28],[18,13,1],[7,12,15],[15,2,3],[29,1,2],[29,2,3],[29,2,4],[29,5,4],[29,23,22],[3,26,5],[3,26,4],[3,25,3],[10,11,2],[30,1,2],[30,3,4],[30,4,5],[30,8,9],[30,18,19],[30,20,13],[6,22,23],[6,24,15],[18,1,2],[18,2,3],[18,4,5],[18,16,1],[24,26,27],[10, 2, 7], [10, 13, 14], [10, 5, 9], [6, 3, 8], [10, 26, 27], [10, 19, 16], [10, 25, 23], [10, 12, 15], [10, 29, 30], [10, 20, 21],[27,28,30],[28,29,30],[10,2,1],[10,7,8],[10,13,14],[10,11,8],[15,1,2],[15,8,4],[13,14,15],[11,12,15],[22,1,2],[22,21,3],[22,25,23],[10,4,8],[17,2,3],[17,2,4],[17,20,21],[18,2,3],[18,2,4],[18,19,16],[15,4,9],[4,5,1],[4,5,10],[5,7,9],[4,5,9]]
# Need a prime
# to help spread
# 3sets apart.
count = len(s)//3
while True:
count = count + 1
if sympy.isprime(count) == True:
prime = count
break
# I'm going to need this for
# my formula.
# Here, I am counting
# all possible Three Element
# combinations.
# But, its 241 times larger
# 241 is prime. Theortically,
# this should space them out
# better.
combinations_count = len(s)*241*((len(s)*241)1)*((len(s)*241)2)//6
combinations_three = len(s)*1*((len(s)*1)1)*((len(s)*1)2)//6
# The formula I need
# to use to calculate
# odds of finding
# a len(s)//3 length
# solution.
p = (len(s)//3)/combinations_count * 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
if len(c) >= len(s)//3*2:
for jj in combinations(c[0:len(s)//3*2], len(s)//3):
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()
if len(c) >= len(s)//3*2:
X = list(reversed(c))
for jj in combinations(X[0:len(s)//3*2], len(s)//3):
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):
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()
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
# Shuffle these
# annoying
# counterexamples
# that might ruin
# my day
# Using prime number to help
# spread apart. Its NOT
# nonsequitir. Primes
# have been observed...
Read more »