Print Permutations

PrintPermutations.java

import java.util.*;

public class permutations
{
  public static void main(String[] args)
  {
    String str = new String("abc");
    StringBuffer output = new StringBuffer();

    boolean used[] = {false, false, false};

    permute.printPermutations(0, output, used, str);
  }
}


public class permute{

  static void printPermutations(int level, StringBuffer output, boolean used[], String orig){
      int len = orig.length();
      if (level == len){
          System.out.println(output);
      }
      else{
          for (int i = 0; i < len; i++){    
              //recurse if not used already
              if (!used[i]){
                  output.append(orig.charAt(i));
                  used[i] = true;
                  printPermutations(level+1, output, used, orig);
                  output.deleteCharAt(output.length() - 1);
                  used[i] = false;
              }
          }
      }
  }
}

/*Output:

abc
acb
bac
bca
cab
cba

*/


//Variation:

public class Solution {
    public String getPermutation(int n, int k) {
        StringBuffer num = new StringBuffer();
        for (int i = 1; i <= n; i++){
            num.append((new Integer(i)).toString());
        }
        String str = num.toString();
        
        if (str.length() == 1 && k == 1) return str;
        
        boolean[] used = new boolean[str.length()];
        StringBuffer strBuff = new StringBuffer();
        ArrayList<String> list= new ArrayList<String>();
        
        getPermHelper(str, strBuff, 0, used, list);
        
        return list.get(k-1);
    }
    
    public void getPermHelper(String orig, StringBuffer output, int level, boolean[] used, ArrayList list){
        if (level == orig.length()){
            list.add(output.toString());
        }
        else{
            for (int i = 0; i < orig.length(); i++){    
              //recurse if not used already
              if (!used[i]){
                  output.append(orig.charAt(i));
                  used[i] = true;
                  getPermHelper(orig, output, level+1, used, list);
                  output.deleteCharAt(output.length() - 1);
                  used[i] = false;
              }
          }
            
            
        }
        
    }
}