# Probabilistic Greedy Algorithm for an NP-complete problem

A project log for Attempt @ BPP algorithim for an NP-hard problem

Exact Three Cover.

Tea B 07/11/2020 at 19:590 Comments
```import random
from itertools import combinations
from itertools import permutations
import sympy
import json
import quantumrandom

print('Welcome to  EX3C-Probablistic-Algorithim')
print('Enter your Exact Three Cover Instance')

s =  input("Input list of integers (no repeating elements) for S with commas (eg. 1,2,3,4...) : ").split(',')
c =  input('enter list for C (eg. [[1,2,3],[4,5,6]]): ')

#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],[1,2,45],[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]]
# [[1,2,3],[4,5,6],[4,5,7],[4,5,9],[4,6,9],[4,3,2],[4,7,8],[4,1,5],[1,2,4],[1,8,9],[2,7,8],[9,4,6],[5,1,3]]

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

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)

if len(c) <= len(s)//3*2:
print('no')
quit()

# Please note that all items in lists are sorted
# from smallest to largest . I did this because
# I wanted to experiment with ordering and
# how the algorithm selects lists based on
# orderings!

# Experimenting with
# patterns in Primes.

count = len(s)//3
while True:
count += 1
if sympy.isprime(count):
prime = count
break

n = len(s)

# I need a large polynomial constant
# to solve large instances of Exact
# three cover. Naive method would
# take forever.

while_loop_steps = n*241*((n*241)-1)*((n*241)-2)//6

#p = (len(s)//3)/while_loop_steps * 100

if len(s) % 3 != 0:
print('invalid input')
quit()

# Sort list to remove
# lists like [1,2,3] and [1,3,2]
# but leave [1,2,3].
# If I wanted too use Brute force
# just needs one. Shortens list
# and improves execution time.

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 lists
# 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 lists
# 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 lists

c = [c[x] for x in range(len(c)) if not(c[x] in c[:x])]

# sort list from smallest to largest
new_c = []
for a in range(0, len(c)):
new_c.append(sorted(tuple(c[a])))

# sort c into like lists
# (eg. [1,2,x], with all [1,2,x]'s

sorted_new_c = []
for a in range(0, len(new_c)):
for b in new_c[a+1:]:
if c[a][0] == b[0]:
if c[a][1] == b[1]:
sorted_new_c.append(b)
sorted_new_c.append(c[a])

# remove repeating lists
sorted_new_c = [sorted_new_c[x] for x in range(len(sorted_new_c)) if not(sorted_new_c[x] in sorted_new_c[:x])]

# I don't want to forget the other lists
surpise_second_while_loop = []
for a in new_c:
if a not in sorted_new_c:
surpise_second_while_loop.append(a)
sorted_new_c.append(a)

c = sorted_new_c

stop = 0
Potential_solution = []
opps = 0
failed_lists = 0
ss = s

# add seed to the PRNG
# In the original Algorithim
# you are suppose to use
# your own QRNG (quantum random number generator)
# And then create a for loop that has len(c) steps.

# online server. 10,000+ requests is a bad idea!!
# SO DO NOT CHANGE THE LOOP VALUES BELOW!!
for a in range(0, 20):
o = quantumrandom.randint(0, len(c))
random.seed(int(o))

def shuff(c, n):
for i in range(n-1,0,-1):
j = random.randint(0,i)
c[i],c[j] = c[j],c[i]

c.append(c[len(c)-1])

# use value prime to pre-shuffle list C
for a in range(0, prime+1):
shuff(c,len(c))

# while loop to see
# if we can find
# an Exact Three Cover
# in poly-time.

while stop <= while_loop_steps:

# Shuffling c randomly
# this seems to help
# select a correct list

shuff(c,len(c))
opps = opps + 1
stop = stop + 1

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_lists = failed_lists + 1
quit()

# opps helps
# me see
# if I miss a correct
# list

if opps > len(c):
if failed_lists < 1:
s = set()
opps = 0
sorted_new_c = []
for a in range(0, len(new_c)):
for b in new_c[a+1:]:
if c[a][0] == b[0]:
if c[a][1] == b[1]:
sorted_new_c.append(b)
sorted_new_c.append(c[a])
sorted_new_c = [sorted_new_c[x] for x in range(len(sorted_new_c)) if not(sorted_new_c[x] in sorted_new_c[:x])]
surpise_second_while_loop = []
for a in new_c:
if a not in sorted_new_c:
surpise_second_while_loop.append(a)
sorted_new_c.append(a)
c = sorted_new_c

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

# I just found out
# I could filter some
# cases so run it a second time

stop = 0
Potential_solution = []
opps = 0
failed_lists = 0

c = surpise_second_while_loop

while stop <= while_loop_steps:

# Shuffling c randomly
# this seems to help
# select a correct list
opps = opps + 1
stop = stop + 1

shuff(c,len(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_lists = failed_lists + 1
quit()

# opps helps
# me see
# if I miss a correct
# list

if opps > len(c):
if failed_lists < 1:
s = set()
opps = 0
sorted_new_c = []
for a in range(0, len(new_c)):
for b in new_c[a+1:]:
if c[a][0] == b[0]:
if c[a][1] == b[1]:
sorted_new_c.append(b)
sorted_new_c.append(c[a])
sorted_new_c = [sorted_new_c[x] for x in range(len(sorted_new_c)) if not(sorted_new_c[x] in sorted_new_c[:x])]
surpise_second_while_loop = []
for a in new_c:
if a not in sorted_new_c:
surpise_second_while_loop.append(a)
sorted_new_c.append(a)
c = sorted_new_c

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

print('no')```