backtracking-generare-perm.java

backtracking-generare-perm.java

import java.io.*;
import java.util.Scanner;
/*
1 2 3
1 3 2
.....
3 2 1
n! = 1 * 2 * ... * n
*/

//complexitate O(n!)
public class Permutations {
	
      private static final int MAX = 300;
      private static int n;
      private static int[] perm = new int[MAX];


      public static void main(String[] args) throws IOException {

            n = readInput("perm.in");
            BufferedWriter fout = new BufferedWriter(new FileWriter("perm.out"));
            solve(fout);
            fout.close();
      }

      private static int readInput(String filename) throws IOException {

      	    Scanner scanner = new Scanner(new File(filename));
      	    int val =  scanner.nextInt();
      	    scanner.close();
      	    return val;
      }

      private static void solve(BufferedWriter fout) throws IOException {
               
               int level = 1;
               perm[ level ] = 0;

               while( level > 0 ) {

                     boolean found  = false;

                      //cautam un succesor valid
                     while(perm[level] < n) {
                     	  perm[level]++;
                     	  if(isValid(level)) {
                     	  	found = true;
                           break;
                     	  }
                     }    


                     if( found ) {

                        if(level == n) {

                            printSolution(fout);

                        } else {

                           level++;//urcam

                           perm[level] = 0;//initializam pe nivelul urmator

                        }

                     } else {

                        perm[level] = 0; //reset la parasire nivel
                        level--; //nivel inferior; coboram
                     }
               }
         
      }


      private static boolean isValid(int level) {

         for(int i = 1; i < level; ++i) {
            if(perm[i] == perm[level]) return false;
         }
         return true;
      }

      private static void printSolution(BufferedWriter fout) throws IOException {

          StringBuilder sb = new StringBuilder();

          for(int i = 1; i <= n; ++i) {
            sb.append(perm[i]).append(" ");
          }

          System.out.println(sb);
          fout.write(sb.toString());
          fout.newLine();
      }
 
}

/*

 stiva: perm

level 3: 
level 2: 
level 1: 
        0

3! = 6
tipareste solutia : 1 2 3
                    1 3 2
                    2 1 3 
                    2 3 1
                    3 1 2
                    3 2 1
*/