• The Algorithm itself

    Tea B06/19/2020 at 01:14 0 comments

    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
    # counter-examples
    # that might ruin
    # my day
    
    
    # Using prime number to help
    # spread apart. Its NOT
    # non-sequitir. Primes
    # have been observed...
    Read more »