#include <math.h>
#include <stdio.h>
#include <string.h>

#define max(a,b)(((a)>(b))?(a):(b))
#define min(a,b)(((a)<(b))?(a):(b))

/*
This script is used to compute an upper bound on the number of possible orderings of self-multiplication.
See this blog post: http://www.njohnston.ca/2014/02/counting-the-possible-orderings-of-pairwise-multiplication/

Author: Nathaniel Johnston (nathaniel@njohnston.ca)
Version: 1.00
Last Updated: Feb. 12, 2014
*/

unsigned short int a[100][100], numPool[10000];
unsigned short int n;
unsigned int ct;
FILE *fp;

void fillGrid(short int i,short int j,short int lLim);
unsigned int checkOrdered(short int i2,short int j2);
unsigned int checkCross();
unsigned int checkCrossB();

int main()
{
    unsigned int i0,j0;

    printf("This tool will provide an upper bound on the number of possible orderings of pairwise multiplication of n positive real numbers. Please enter n: ");
    scanf("%d",&n);

    for(i0=0; i0<n; i0++){
        for(j0=0; j0<n; j0++){
            a[i0][j0] = 10000;
        }
    }

    for(i0=1; i0<=n*(n+1)/2; i0++){
        numPool[i0] = 1;
    }

    ct = 0;

    // the two top-left and bottom-right entries of the matrix are always the same, so fix them
    a[0][0] = 1;
    a[0][1] = 2;
    a[n-1][n-1] = n*(n+1)/2;
    a[n-2][n-1] = n*(n+1)/2 - 1;

    // now recursively fill the matrix
    fillGrid(0,2,3);

    if(ct == 0){
        printf("\nDone searching -- no orderings found.\n",n);
    }else{
        printf("\nFound %d possible orderings.\n",ct);
    }
    getchar();

    return 0;
}

// this function recursively fills the matrix
void fillGrid(short int i,short int j,short int lLim)
{
    int k,uLim;

    uLim = j*(j+1)/2 + i*(n-j) + 1;

    for(k=lLim; k<=uLim; k++){
        if(numPool[k] == 1){
            a[i][j] = k;
            numPool[k] = 0;

            if(checkOrdered(i,j)){
                if(i == n-2 && j == n-2){
                    if(checkCross() && checkCrossB()){
                        ct++;
                    }
                }else if(j == n-1){
                    fillGrid(i+1,i+1,3);
                }else{
                    fillGrid(i,j+1,k+1);
                }
            }
            numPool[k] = 1;
        }
    }
    a[i][j] = 10000;
}

// this function checks the columns of the matrix to make sure that they are decreasing (actually, this entire script searches for matrices with *increasing* rows/columns, but the end count will be the same)
unsigned int checkOrdered(short int i2,short int j2)
{
    unsigned short int i3,j3;

    for(j3=2; j3<n; j3++){
        for(i3=0; i3<i2; i3++){
            if(a[i3][j3] > a[i3+1][j3]){
                return 0;
            }
        }
    }

    return 1;
}

// this function checks to see if the weird constraint presented in the section "A Better Upper Bound" of the blog post is satisfied
unsigned int checkCross()
{
    unsigned short int j,k,l,m,g,x;

    for(j=0; j<n-3; j++){ // j: row
        for(k=3; k<n; k++){ // k: column
            for(m=0; m<n-2; m++){ // m: row
                for(l=1; l<n; l++){ // l: column
                    for(x=0; x<n-1; x++){ // x: row
                        for(g=1; g<n; g++){ // g: column
                            if(a[min(j,k)][max(j,k)] > a[min(m,l)][max(m,l)] && a[min(l,g)][max(l,g)] > a[min(k,x)][max(k,x)] && a[min(j,g)][max(j,g)] < a[min(m,x)][max(m,x)]){
                                return 0;
                            }
                        }
                    }
                }
            }
        }
    }

    return 1;
}

// this function checks to see if the even weirder constraint presented in the section "This Bound is Not Tight" of the blog post is satisfied
// this code is still really messy, mainly for speed reasons
unsigned int checkCrossB()
{
    unsigned short int j0,j1,j2,j3,j4,j5;

    if(n >= 6){
        if(a[0][4] > a[1][1] && a[1][3] > a[2][2] && a[1][4] > a[3][3] && a[2][3] > a[0][5] && a[2][5] > a[4][4]){
            return 0;
        }

        if(a[0][4] < a[1][1] && a[1][3] < a[2][2] && a[1][4] < a[3][3] && a[2][3] < a[0][5] && a[2][5] < a[4][4]){
            return 0;
        }

        if(a[1][5] < a[4][4] && a[2][4] < a[3][3] && a[1][4] < a[2][2] && a[2][3] < a[0][5] && a[0][3] < a[1][1]){
            return 0;
        }

        if(a[1][5] > a[4][4] && a[2][4] > a[3][3] && a[1][4] > a[2][2] && a[2][3] > a[0][5] && a[0][3] > a[1][1]){
            return 0;
        }
    }

    if(n >= 7){
        for(j5=5; j5<=6; j5++){
            for(j4=4; j4<j5; j4++){
                for(j3=3; j3<j4; j3++){
                    for(j2=2; j2<j3; j2++){
                        for(j1=1; j1<j2; j1++){
                            for(j0=0; j0<j1; j0++){
                                if(a[j0][j4] > a[j1][j1] && a[j1][j3] > a[j2][j2] && a[j1][j4] > a[j3][j3] && a[j2][j3] > a[j0][j5] && a[j2][j5] > a[j4][j4]){
                                    return 0;
                                }

                                if(a[j0][j4] < a[j1][j1] && a[j1][j3] < a[j2][j2] && a[j1][j4] < a[j3][j3] && a[j2][j3] < a[j0][j5] && a[j2][j5] < a[j4][j4]){
                                    return 0;
                                }

                                if(a[j1][j5] < a[j4][j4] && a[j2][j4] < a[j3][j3] && a[j1][j4] < a[j2][j2] && a[j2][j3] < a[j0][j5] && a[j0][j3] < a[j1][j1]){
                                    return 0;
                                }

                                if(a[j1][j5] > a[j4][j4] && a[j2][j4] > a[j3][j3] && a[j1][j4] > a[j2][j2] && a[j2][j3] > a[j0][j5] && a[j0][j3] > a[j1][j1]){
                                    return 0;
                                }
                            }
                        }
                    }
                }
            }
        }

        if(a[0][4] > a[1][1] && a[1][3] > a[2][2] && a[1][5] > a[3][3] && a[2][3] > a[0][6] && a[2][6] > a[4][5]){
            return 0;
        }
        if(a[0][5] > a[1][1] && a[1][3] > a[2][2] && a[1][4] > a[3][3] && a[2][3] > a[0][6] && a[2][6] > a[4][5]){
            return 0;
        }
        if(a[0][5] > a[1][1] && a[1][4] > a[2][2] && a[1][5] > a[3][4] && a[2][3] > a[0][6] && a[2][6] > a[5][5]){
            return 0;
        }
        if(a[0][5] > a[1][1] && a[1][3] > a[2][2] && a[1][5] > a[3][4] && a[2][4] > a[0][6] && a[2][6] > a[5][5]){
            return 0;
        }
        if(a[0][5] > a[1][1] && a[1][4] > a[2][3] && a[1][5] > a[4][4] && a[3][4] > a[0][6] && a[2][6] > a[5][5]){
            return 0;
        }
        if(a[0][5] > a[1][1] && a[1][4] > a[2][3] && a[1][5] > a[4][4] && a[2][4] > a[0][6] && a[3][6] > a[5][5]){
            return 0;
        }
        if(a[0][5] > a[1][2] && a[1][4] > a[3][3] && a[2][5] > a[4][4] && a[3][4] > a[0][6] && a[3][6] > a[5][5]){
            return 0;
        }
        if(a[0][5] > a[1][2] && a[2][4] > a[3][3] && a[1][5] > a[4][4] && a[3][4] > a[0][6] && a[3][6] > a[5][5]){
            return 0;
        }

        if(a[0][4] < a[1][1] && a[1][3] < a[2][2] && a[1][5] < a[3][3] && a[2][3] < a[0][6] && a[2][6] < a[4][5]){
            return 0;
        }
        if(a[0][5] < a[1][1] && a[1][3] < a[2][2] && a[1][4] < a[3][3] && a[2][3] < a[0][6] && a[2][6] < a[4][5]){
            return 0;
        }
        if(a[0][5] < a[1][1] && a[1][3] < a[2][2] && a[1][5] < a[3][4] && a[2][4] < a[0][6] && a[2][6] < a[5][5]){
            return 0;
        }
        if(a[0][5] < a[1][1] && a[1][4] < a[2][2] && a[1][5] < a[3][4] && a[2][3] < a[0][6] && a[2][6] < a[5][5]){
            return 0;
        }
        if(a[0][5] < a[1][1] && a[1][4] < a[2][3] && a[1][5] < a[4][4] && a[3][4] < a[0][6] && a[2][6] < a[5][5]){
            return 0;
        }
        if(a[0][5] < a[1][1] && a[1][4] < a[2][3] && a[1][5] < a[4][4] && a[2][4] < a[0][6] && a[3][6] < a[5][5]){
            return 0;
        }
        if(a[0][5] < a[1][2] && a[2][4] < a[3][3] && a[1][5] < a[4][4] && a[3][4] < a[0][6] && a[3][6] < a[5][5]){
            return 0;
        }
        if(a[0][5] < a[1][2] && a[1][4] < a[3][3] && a[2][5] < a[4][4] && a[3][4] < a[0][6] && a[3][6] < a[5][5]){
            return 0;
        }

        if(a[1][6] < a[4][5] && a[2][4] < a[3][3] && a[1][5] < a[2][2] && a[2][3] < a[0][6] && a[0][3] < a[1][1]){
            return 0;
        }
        if(a[1][6] < a[4][5] && a[2][5] < a[3][3] && a[1][4] < a[2][2] && a[2][3] < a[0][6] && a[0][3] < a[1][1]){
            return 0;
        }
        if(a[1][6] < a[5][5] && a[2][5] < a[3][4] && a[1][5] < a[2][2] && a[2][4] < a[0][6] && a[0][3] < a[1][1]){
            return 0;
        }
        if(a[1][6] < a[5][5] && a[2][5] < a[3][4] && a[1][5] < a[2][2] && a[2][3] < a[0][6] && a[0][4] < a[1][1]){
            return 0;
        }
        if(a[1][6] < a[5][5] && a[3][5] < a[4][4] && a[1][5] < a[2][3] && a[2][4] < a[0][6] && a[0][4] < a[1][1]){
            return 0;
        }
        if(a[1][6] < a[5][5] && a[2][5] < a[4][4] && a[1][5] < a[2][3] && a[3][4] < a[0][6] && a[0][4] < a[1][1]){
            return 0;
        }
        if(a[2][6] < a[5][5] && a[3][5] < a[4][4] && a[1][5] < a[3][3] && a[3][4] < a[0][6] && a[0][4] < a[1][2]){
            return 0;
        }
        if(a[1][6] < a[5][5] && a[3][5] < a[4][4] && a[2][5] < a[3][3] && a[3][4] < a[0][6] && a[0][4] < a[1][2]){
            return 0;
        }

        if(a[1][6] > a[4][5] && a[2][5] > a[3][3] && a[1][4] > a[2][2] && a[2][3] > a[0][6] && a[0][3] > a[1][1]){
            return 0;
        }
        if(a[1][6] > a[4][5] && a[2][4] > a[3][3] && a[1][5] > a[2][2] && a[2][3] > a[0][6] && a[0][3] > a[1][1]){
            return 0;
        }
        if(a[1][6] > a[5][5] && a[2][5] > a[3][4] && a[1][5] > a[2][2] && a[2][4] > a[0][6] && a[0][3] > a[1][1]){
            return 0;
        }
        if(a[1][6] > a[5][5] && a[2][5] > a[3][4] && a[1][5] > a[2][2] && a[2][3] > a[0][6] && a[0][4] > a[1][1]){
            return 0;
        }
        if(a[1][6] > a[5][5] && a[3][5] > a[4][4] && a[1][5] > a[2][3] && a[2][4] > a[0][6] && a[0][4] > a[1][1]){
            return 0;
        }
        if(a[1][6] > a[5][5] && a[2][5] > a[4][4] && a[1][5] > a[2][3] && a[3][4] > a[0][6] && a[0][4] > a[1][1]){
            return 0;
        }
        if(a[2][6] > a[5][5] && a[3][5] > a[4][4] && a[1][5] > a[3][3] && a[3][4] > a[0][6] && a[0][4] > a[1][2]){
            return 0;
        }
        if(a[1][6] > a[5][5] && a[3][5] > a[4][4] && a[2][5] > a[3][3] && a[3][4] > a[0][6] && a[0][4] > a[1][2]){
            return 0;
        }
    }

    return 1;
}