2
\$\begingroup\$

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?
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Travis Wells Jun 28 at 23:57
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Zchpyvr Jul 1 at 15:07
  • \$\begingroup\$ @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. \$\endgroup\$ – Travis Wells Jul 16 at 1:47
4
\$\begingroup\$

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

?

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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())) \$\endgroup\$ – Linny Jul 10 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.