def TrainsRecursive(totalN):
    trains = 0;
    initNode = {'num':1,'cut':False,'parent':0}
    frontier = [initNode]
    trainArray = []

    while(len(frontier) > 0):
        node = frontier.pop(len(frontier)-1)
        #check it off the frontier
        if(node["num"] < totalN):
            nodeCut = {}; nodeCut["num"] = node["num"] + 1; nodeCut["cut"] = True; nodeCut["parent"] = node;
            frontier.append(nodeCut)
            nodeSpare = {}; nodeSpare["num"] = node["num"] + 1; nodeSpare["cut"] = False;  nodeSpare["parent"] = node;
            frontier.append(nodeSpare)
        else:
            fullList = []
            cutArray = []
            cuts = ""
            while(node['parent'] != 0):
                if(node['cut']):
                    cuts = cuts + "1"
                    cutArray.append(1)
                else:
                    cuts = cuts + "0"
                    cutArray.append(0)
                fullList.append(node['parent'])
                node = node['parent']


            #print(cuts)
            #translate cuts to rods

            rodLength = 1;
            rodArray = []
            for i in range(len(cutArray)):
                cut = cutArray[i];
                if(cut == 1):
                    rodArray.append(rodLength)
                    rodLength = 1
                else:
                    rodLength = rodLength + 1;

            rodArray.append(rodLength)
            trainArray.append(rodArray)

            trains +=1;

    #sort them
    sortedRodArray = []
    num = 1;
    while(True):

        found = False;
        for i in range(len(trainArray)):
            if(len(trainArray[i]) == num):
                sortedRodArray.append(trainArray[i])
                found = True;

        if(found == False):
            break;
        num += 1;

    #pretty print
    noOnes = 0;
    for i in range(len(sortedRodArray)):
        foundOne = False;
        for j in range(len(sortedRodArray[i])):
            if(sortedRodArray[i][j] == 1):
                foundOne = True;
        if(foundOne == False):
            noOnes += 1;

    return sortedRodArray

def TrainsWithParts(trains,k):
    #takes an array of trains, and an integer k, removes all trains whose len() is more than k
    newTrains = []
    for i in range(len(trains)):
        arr = trains[i];
        if(len(arr) <= k):
            newTrains.append(arr)

    return newTrains;

def TrainsWithAtMost(trains,k):
    #takes an array of trains, and an integer k. Removes all trains that contain a rod with a length greater than k
    newTrains = []
    for i in range(len(trains)):
        arr = trains[i];
        Found = True;
        for j in range(len(arr)):
            if(arr[j] > k):
                Found = False;

        if(Found):
            newTrains.append(arr)

    return newTrains;

def Unordered(trains):
    #Removes duplicates ex: [1,4] and [4,1] are considered to be the same

    for i in range(len(trains)):
        trains[i].sort();

    hashed = {}

    newTrains = []
    for arr in trains:
        signature = ""
        for j in arr:
            signature += str(j)
        if(not(signature in hashed)):
            hashed[signature] = True;
            newTrains.append(arr)

    return newTrains

def Triangles(trains):
    #Takes a q_3(n-3), adds missing pieces and returns all the valid triangle
    #A valid triangle is such that:
    #a < b + c
    #a > b > c > 0
    return 0.

def Distinct(trains):
    #This function removes all trains that have non-unique parts

    newTrains = []

    for train in trains:
        FoundDuplicate = False;
        numHash = {};
        for j in train:
            if(j in numHash):
                FoundDuplicate = True;
                break;
            numHash[j] = True;
        if(not FoundDuplicate):
            newTrains.append(train)

    return newTrains;


TRAIN_LENGTH = 9;
PARTS = 3;

allTrains = TrainsRecursive(TRAIN_LENGTH);

print("Total " + str(len(allTrains)))

# newPartsTrains = TrainsWithParts(allTrains,PARTS);
# newPartsTrains = Unordered(newPartsTrains);

# print(" ")
# print("q_" + str(PARTS) + "(" + str(TRAIN_LENGTH) + ") = " +  str(len(newPartsTrains)))
# print(" ")

# for train in newPartsTrains:
#   print(train)

# newTrains = TrainsWithAtMost(allTrains,PARTS);
# newTrains = Unordered(newTrains);

# print(" ")
# print("p_" + str(PARTS) + "(" + str(TRAIN_LENGTH) + ") = " +  str(len(newTrains)))
# print(" ")

# for train in newTrains:
#   print(train)

# uTrains = Distinct(newTrains)

# print(" ")
# print("Unique = " + str(len(uTrains)))
# print(" ")



# for train in uTrains:
#   print(train)

n = 11;

# For k = 3, the differences between PN and UN were 3 3, 4 4, 5 5, 6 6 etc..

# for i in range(3,15):
#   print("--------------- n = " + str(i) + " k = " + str(k))
#   totalTrains = TrainsRecursive(i);
#   pTrains = TrainsWithParts(totalTrains,k)
#   pTrains = Unordered(pTrains)

#   uTrains = Distinct(pTrains)

#   print("PN = " + str(len(pTrains)))
#   print("UN = " +  str(len(uTrains)))
#   print("PN - UN = " + str(len(pTrains) - len(uTrains)))

totalTrains = TrainsRecursive(n)
pTrains = TrainsWithParts(totalTrains,5)
pTrains = Unordered(pTrains)

uTrains = Distinct(pTrains)

for train in pTrains:
    print(train)

print("==============")

for train in uTrains:
    print(train)