generateSteiner.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon Jan 18 10:20:50 2021

@author: lukepatton
"""

import math

# This function will generate the inductor sequence for a ns1d0 sequence.
# It is important to note that while ns1d0 sequences are numbered from 0,
# the inductor sequences are numbered starting at 1 in the paper. For this
# reason, I will generate a list with a -1 in the 0 index so the proper indices 
# can start at 1.

# input: ns1d0, a valid ns1d0 sequence (list of ints)
# output: the inductor sequence for that ns1d0 (list of ints)
def generateInductor(ns1d0):
    # n - 1 will be the length of the inductor sequence.
    
    n = len(ns1d0) * 2 - 1
    inductor = [-1 for i in range(n)]
    for i in range(1, int(((n-1)/2) + 1)):
        first = ns1d0[i] - ns1d0[i-1]
        second = ns1d0[i-1] - ns1d0[i]
        
        inductor[first] = ns1d0[i]
            
        inductor[second] = ns1d0[i - 1]
        
    
    return inductor

# Like with the inductor sequence, the sign sequence starts its numbering at 1,
# so i will leave a 0 in the 0 index of the list so that the proper indeces
# will start at 1. Additionally, I will use -1 and +1 to represent - and +, 
# respectively.
    
# input: ns1d0, a valid ns1d0 sequence (list of ints)
# output: the sign-inductor for that ns1d0 (list of ints)
def generateSignInductor(ns1d0):
    n = len(ns1d0) * 2 - 1
    sign_inductor = [0 for i in range(n)]
    for i in range(1, int(((n-1)/2) + 1)):
        first = ns1d0[i] - ns1d0[i-1]
        second = ns1d0[i-1] - ns1d0[i]
        
        sign_inductor[first] = pow(-1, i - 1)
        sign_inductor[second] = pow(-1, i - 1)
    
    return sign_inductor


# This function will take an ns1d0 sequence and return the Steiner Triple
# System induced by it. The triple system will be a list of lists. Each sublist
# will represent a triple.

# input: ns1d0, a valid ns1d0 sequence of order n (list of ints)
# output: the STS induced by that sequence (list of lists of ints)
def generateSteinerTripleSystem(ns1d0):
    n = len(ns1d0) * 2 - 1
    inductor = generateInductor(ns1d0)
    sign_inductor = generateSignInductor(ns1d0)
    sets_of_two = allPairsInList(list(range(n)))
    T = []
    for set_of_two in sets_of_two:
        a = set_of_two[0]
        b = set_of_two[1]
        c = specialOperator(a,b,inductor)
        item = [[a,0], [c,1], [b,-1]]
        T.append(item)
    
    indexing_set =[[a,i] for a in range(n) for i in range(3)]

    steiner_set = [[indexing_set.index([a,0]), indexing_set.index([a,1]), indexing_set.index([a,2])] for a in range(n) ]
    
    for t in T:
        for j in range(3):
            item_one = indexing_set.index([t[0][0],j])
            item_two = indexing_set.index([t[1][0], (j + sign_inductor[t[0][0] - t[2][0]]) % 3])
            item_three = indexing_set.index([t[2][0], j])
            steiner_set.append([item_one, item_two, item_three])
    return steiner_set
        
# This function validates that the STS given to it is valid by generating all 
# the pairs for that sequence and asserting that they are contained in exactly
# one triple in the system.
    
# input: system, an STS (list of list of ints) and v, the order of that STS (int)
# output: whether the system is valid (bool)
def checkSteinerTripleSystem(system, v):
    pairs = allPairsInList(list(range(v)))
    for pair in pairs:
        pair_count = 0
        for triple in system:
            if pair[0] in triple and pair[1] in triple:
                pair_count+=1
        if pair_count != 1:
            return False
    return True
            
    
# This function generates all the pairs of objects in a given list of numbers, 
# specifically it generates combinations rather than permutations (i.e. if a, b
# is in the list of pairs, then b, a will not be).

# input: a list of objects (list of objects of type i)
# output: all pairs of those objects (list of lists of objects of type i)
def allPairsInList(objectList):
    combinations = allPermutationsOfLength(objectList,2)
    for [a,b] in combinations:
        if [b,a] in combinations:
            combinations.remove([b,a])
            
    return combinations
        
# This function generates all permutations of a certain length from a list of 
# objects. Since they are permutations, sequences containing the same objects
# in a different order will occur (e.g. if 1,2,3 is a permutation, 3,2,1 will 
# be as well).
    
# input: a list of objects (list of objects of type i), a length (int)
# output: all permutations of the given length  of those objects 
# (list of lists of objects of type i)
def allPermutationsOfLength(objectList, length):
    if length == 0:
        return [[]]
    else:
        combos = []
        for number in objectList:
            subList = objectList.copy()
            subList.remove(number)
            subCombos = allPermutationsOfLength(subList, length-1)
            for combo in subCombos:
                combo.append(number)
                combos.append(combo)
        return combos


# This function will perform the circle operator on i and j, given the inductor
# sequence provided.

# input: the numbers on which the operator should be performed (int), and the 
# inductor sequence with which to perform the operator (list of ints)
# output: the result of the operator (int)
def specialOperator(i, j, inductor):
    n= len(inductor)
    if i == j:
        return i
    else:
        return (i - inductor[i-j] + math.ceil(n/2)) % n