/** 
 * Permutation enumeration of 1324 and 2143 with {2<->3}
 * also useful for hunting for certain degree sequences
 */
class PermEnumerate {
    public static void main(String[] args) {
    int nSize=6;  /* nSize is the size of the permutation group we consider */
    int posEdges=(nSize*nSize/4);
    int TotalAvoiding=0, TotalConnected=0, edgesum, TotalTrees=0;
    int[] perm = new int[20];
    int[] degree = new int[20];
    int[] edges = new int [100];
/* rrr, sss, ttt denote the sum of the degrees, sum of the degrees squared
 * and the sum of the degrees cubed, respectively */
    int rrr=14, sss=34, ttt=86;
    
/* initialize the permutation */
    for(int i=0; i<= nSize; i++) { perm[i]=i; }

    int done=0;
    do{
    int qi,qj,qk,ql,qm, avoiding=1, connected=1;

/* test for 1324 avoidance */
    for(qi=1; qi <= nSize-3; qi++) {
     for(qj=qi+1; qj <= nSize-2; qj++) {
      if(perm[qj] > perm[qi]) {
       for(qk=qj+1; qk <= nSize-1; qk++) {
        if(perm[qk] > perm[qi] && perm[qk] < perm[qj]) {
         for(ql=qk+1; ql <= nSize; ql++) {
          if(perm[ql] > perm[qj]) {
           avoiding=0;
    }}}}}}}
    
/* test for 2143 {2<->3} avoidance */
    if(avoiding==1) {
    for(qi=1; qi <= nSize-3; qi++) {
     for(qj=qi+1; qj <= nSize-2; qj++) {
      if(perm[qj] < perm[qi]) {
       for(qk=qj+1; qk <= nSize-1; qk++) {
        if(perm[qk] > perm[qi]) {
         for(ql=qk+1; ql <= nSize; ql++) {
          if(perm[ql] > perm[qi] && perm[ql] < perm[qk]) {
           int BarTest=1;
           for(qm=qi+1; qm<ql; qm++) {
	    if(perm[qi]<perm[qm]&&perm[qm]<perm[ql]) { BarTest = 0; } }
           if(BarTest==1) { avoiding=0; }
    }}}}}}}}

/* update totals */	    
    if(avoiding==1) ++TotalAvoiding;
    
/* test for connected */
    for(qi=1; qi<nSize; qi++){
     qk=perm[1]; ql=perm[nSize];	    
     for(qj=1; qj<= qi; qj++) {
      if(perm[qj]<qk) qk=perm[qj];
     }
     for(qj=qi+1;qj<=nSize;qj++) {
      if(perm[qj]>ql) ql=perm[qj];
     }
     if(qk>ql) connected=0;
    }

/* Tree count */
    if(avoiding==1&&connected==1) TotalTrees++;
    
/* update connected count */	    
    if(connected==1) ++TotalConnected;
    
/* generate degree sequence */
    for(qi=1;qi<=nSize;qi++) degree[qi]=0;
    for(qi=1;qi<=nSize;qi++){
     qk=0;
     for(qj=qi; qj>=1; qj--){
      if(perm[qj]>qk && perm[qj]<perm[qi]){
       qk=perm[qj]; degree[qi]++;
      }
     }
     qk=nSize+1;
     for(qj=qi; qj<=nSize; qj++){
      if(perm[qj]<qk && perm[qj]>perm[qi]){
       qk=perm[qj]; degree[qi]++;
      }
     }
    }
    
/* update edge count */    
    edgesum=0; for(qi=1;qi<=nSize;qi++) edgesum=edgesum+degree[qi];
    edges[(edgesum/2)]++;

    int rr=0, ss=0, tt=0;
    for(qi=1;qi<=nSize;qi++){
    rr=rr+degree[qi];
    ss=ss+degree[qi]*degree[qi];
    tt=tt+degree[qi]*degree[qi]*degree[qi];
    }
    
    if(rr==rrr && ss==sss && tt==ttt)
     /* print out the permutation and the degree sequence, add more terms if 
      * considering a larger permutation */
     System.out.println("" + perm[1] + perm[2] + perm[3] + perm[4] + perm[5] + perm[6] + perm[7] + perm[8] + "-" + degree[1] + degree[2] + degree[3] + degree[4] + degree[5] + degree[6] + degree[7] + degree[8]);
    
    /* advance to the next permutation */
    int pi=nSize-1,pj=nSize,pk;
    while(perm[pi]>perm[pi + 1]){ --pi; }
    if(pi==0) done=1;
    else{
	while(perm[pi]>perm[pj]){ --pj; }
	pk=perm[pi]; perm[pi]=perm[pj]; perm[pj]=pk;
	++pi; pj=nSize;
	while (pi<pj){
	pk=perm[pi]; perm[pi]=perm[pj]; perm[pj]=pk;
        ++pi; --pj;
        }
    }
    } while(done==0);
    System.out.println("Avoiding: " + TotalAvoiding);
    System.out.println("Connected: " + TotalConnected);
    System.out.println("Connected trees: " + TotalTrees);
    for (int qq=0; qq<=posEdges; qq++)
    System.out.println(qq+ " edges: " + edges[qq]); /* distribution of edges */
    }
}