// permute2.java         a more symmetric generator
//                       compile  javac -cp . permute2.java
//                       execute  java  -cp . permute
// really big for n=10   3,628,800  permutations of 1 2 3 4 5 6 7 8 9 10
// 1! = 1   2! = 2   3! = 6    4! = 24   5! = 120    6! = 720   
// 7! =   5,040   8! =  40,320    9! = 362,880 
// This is a sequential generation of the permutations of 1..n
// Each higher number of permuattions uses the previous group ().
// e.g. 1p = (1)   2p1 = 1(1+1) = (1 2)  2p2 =2 (1) = (2 1)
// e.g. 3p11 = 1(1+1 2+1) = (1 2 3) increment previous 1 and above
//      3p12 = 1(2+1 1+1) = (1 3 2)
//      3p21 = 2(1   2+1) = (2 1 3) increment previous 2 and above
//      3p22 = 2(2+1 1  ) = (2 3 1)
//      3p31 = 3(1 2)     = (3 1 2) increment previous 3 and above
//      3p32 = 3(2 1)     = (3 2 1)
//        ^^ count previous perm
//        |count 1..n

public class permute2 // each permutation generated using previous permuatation
{
  int n = 7; // this max perm, can be changed, n! can be computed for nt
  int tp[] = {0, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800}; 
  int perm2[][] = {{1,2},{2,1}}; // initialized
  int perm3[][] = new int[6][3];
  int perm4[][] = new int[24][4];
  int perm5[][] = new int[120][5];
  int perm6[][] = new int[720][6];
  int perm7[][] = new int[5040][7];
  		     
  public permute2()
  {
    System.out.println("pemute2.java running");
    prt_perm(2);
    for(int np=3; np<=n; np++)
    {
      gen_perm(np);
      prt_perm(np);
    }
  }

  void gen_perm(int np)
  {
    int ntp = tp[np];    // terms to generate
    int ntpp = tp[np-1]; // previous perm terma
    int jj, k = 0;
    for(int i=0; i<np; i++) // generate np groups
    {
      for(int ii=0; ii<tp[np-1]; ii++) // use for index of previous perm
      {
        jj = i*ntpp+ii;
        for(int j=1; j<np; j++) // copying from previous np
        {
          switch(np)
          {
	    case 3: perm3[jj][0]=i+1;
	            k=perm2[ii][j-1];
	            if(k>i) {k++;}
	            perm3[jj][j] = k;
	    break;
            case 4: perm4[jj][0]=i+1;
		    k=perm3[ii][j-1];
	            if(k>i) {k++;}
	            perm4[jj][j] = k;
	    break;
            case 5: perm5[jj][0]=i+1;
		    k=perm4[ii][j-1];
	            if(k>i) {k++;}
	            perm5[jj][j] = k;
	    break;
            case 6: perm6[jj][0]=i+1;
		    k=perm5[ii][j-1];
	            if(k>i) {k++;}
	            perm6[jj][j] = k;
	    break;
            case 7: perm7[jj][0]=i+1;
		    k=perm6[ii][j-1];
	            if(k>i) {k++;}
	            perm7[jj][j] = k;
	    break;
          } // end switch
        } // end j
      } // end ii
    } // end i
      
  } // end gen_perm

  void prt_perm(int np)
  {
    int ntp = tp[np];
    System.out.println("permutation of "+np+" integers with "+ntp+" terms");
    for(int i=0; i<ntp; i++)
    {
      System.out.print("(");
      for(int j=0; j<np; j++)
      {
	switch(np)
	{
	  case 2: System.out.print(perm2[i][j]+" "); break;
	  case 3: System.out.print(perm3[i][j]+" "); break;
	  case 4: System.out.print(perm4[i][j]+" "); break;
	  case 5: System.out.print(perm5[i][j]+" "); break;
	  case 6: System.out.print(perm6[i][j]+" "); break;
	  case 7: System.out.print(perm7[i][j]+" "); break;
	} // end switch
      } // end j
      System.out.println(") ");
    } // end i
  } // end prt_perm
    
  public static void main (String[] args)
  {
    new permute2();
  }
} // end permute2.java