#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Jan 10 22:58:37 2021

@author: lukepatton
"""
import math


# This function will generate all the possible NS1D0 sequences by generating
# all lists of the appropriate length - 2 of numbers between 2 and n and
# attaching a 0 at the beginning and a 1 at the end.

# input: the desired order of the sequence (int)
# output: all possible sequences from that n (list of lists of ints)
def allSequences(n):
    numberList = list(range(2,n))
    length = math.ceil(n/2)
    
    subSequences=allPermutationsOfLength(numberList, length - 2)
    sequences = []
    for subSequence in subSequences:
        subSequence = [0] + subSequence + [1]
        sequences.append(subSequence)
    return sequences
    
    
# This function checks that the list given has the appropriate length

# input: a sequence, that sequence's order (list of ints, int)
# output: whether that sequence has the correct length (bool)
def checkConditionSize(sequence, n):
    return len(sequence) == math.ceil(n/2)


# This function checks that the list given meets the first rule of NS1D0
# sequences (it starts with a 0 and ends with a 1)

# input: a sequence, that sequence's order (list of ints, int)
# output: whether that sequence meets rule 1 (bool)
def checkCondition1(sequence, n):
    return (sequence[0] == 0 and sequence[-1] == 1)


# This function checks that the list given meets the second rule of NS1D0
# sequences (it does not contain n/2 rounded up)

# input: a sequence, that sequence's order (list of ints, int)
# output: whether that sequence meets rule 2 (bool)
def checkCondition2(sequence, n):
    return math.ceil(n/2) not in sequence


# This function checks that the list given meets the third rule of NS1D0
# sequences (it contains either x or 1-x for all x from 2 to n - 1 but not both)

# input: a sequence, that sequence's order (list of ints, int)
# output: whether that sequence meets rule 3 (bool)
def checkCondition3(sequence, n):
    
    for x in range(2, n):
        if (x != math.ceil(n/2)):
            inverseX = (1-x) % n
            if x in sequence and inverseX in sequence or (x not in sequence and inverseX not in sequence):
                return False
        
    return True


# This function checks that the list given meets the third rule of NS1D0
# sequences (for all j between 1 and n, either j or -j can be formed from the 
# difference of two adjacent numbers but not both)

# input: a sequence, that sequence's order (list of ints, int)
# output: whether that sequence meets rule 4 (bool)
def checkCondition4(sequence, n):
    differences = []
    for k in range(1, len(sequence)):
        differences.append((sequence[k] - sequence[k-1]) % n)
    
    for j in range(1, n):
        inverseJ = -j % n
        if j in differences and inverseJ in differences or (j not in differences and inverseJ not in differences):
            return False
    return True
    
# This function generates through brute force all of the ns1d0 sequences of a 
# given order. It grows quickly, and becomes too expensive for n > 17
    
# input: the desired order of NS1D0 sequence (int)
# output: all NS1D0 sequences of that order (list of lists of ints)
def generateNS1D0(n):
    sequenceList = allSequences(n)
    
    finalList = []
    for sequence in sequenceList:
        passes = True
        for function in [checkConditionSize, checkCondition1, checkCondition2, checkCondition3, checkCondition4]:
            if not function(sequence,n):
                passes = False
        if passes:
            finalList.append(sequence)
    
    return finalList



# 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