Permutation.java

import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created by WiNDWAY on 1/30/16.
 * https://github.com/alvin319/competitive-programming/blob/master/Algorithms/Permutation.java
 */


public class P {
    public static void main(String[] args) {
        String testCase = "abc";
        ArrayList<Character> testSet = new ArrayList<>();
        for (Character x : testCase.toCharArray()) {
            testSet.add(x);
        }
        //System.out.println("C");
        //getC(testSet, "", 0);
        //System.out.println("P");
        getP(testSet, "");
        

        //String[][] matrix = {{"a", "b", "c"}, {"a", "b", "c"}, {"a", "b", "c"}};
        //System.out.println("GP");
        //getGP(matrix, "", 0);
    }

    public static void getP(ArrayList<Character> current, String prefix) {
        if (current.size() == 0) {
            System.out.println(prefix);
        } else {
            for (int i = 0; i < current.size(); i++) {
                String newString = prefix + current.get(i);
                ArrayList<Character> newSet = new ArrayList<>(current);
                newSet.remove(i);
                getP(newSet, newString);
            }
        }
    }

    public static void getC(ArrayList<Character> current, String prefix, int index) {
        if (index == current.size()) {
            System.out.println(prefix);
        } else {
            String newString = prefix;
            getC(current, newString, index + 1); // not choosing
            char leftOver = current.get(index);
            newString += leftOver;
            getC(current, newString, index + 1); // choosing
        }
    }

    public static void getGP(String[][] matrix, String prefix, int outerIndex) {
        if (outerIndex == matrix.length) {
            System.out.println(prefix);
        } else {
            String[] current = matrix[outerIndex];
            for (int j = 0; j < current.length; j++) {
                getGP(matrix, prefix + current[j], outerIndex + 1);
            }
        }
    }
}


/*
getP Evaluation
================
getP: [a,b,c] ""
      i = 0; i < 3:
        newString = "a"
        newSet = [b,c]
        getP: [b,c] "a"
              i = 0; i < 2:
                newString = "ab"
                newSet = [c]
                getP: [c] "ab"
                      i = 0; i < 1:
                        newString = "abc"
                        newSet = []
                        getP: [] "abc"
                              print("abc")              ===>
                      i = 1
               i = 1; i < 2:
                 newString = "ac"
                 newSet = [b]
                 getP: [b] "ac"
                       i = 0; i < 1:
                         newString = "acb"
                         newSet = []
                         getP: [] "acb"
                               print("acb")             ===>
                       i = 1
               i = 2
      i = 1; i < 3:
        newString = "b"
        newSet = [a,c]
        getP: [a,c] "b"
              i = 0; i < 2:
                newString = "ba"
                newSet = [c]
                getP: [c] "ba"
                      i = 0; i < 1:
                        newString = "bac"
                        newSet = []
                        getP: [] "bac"
                              print("bac");             ===>
                      i = 1
               i = 1; i < 2:
                 newString = "bc"
                 newSet = [a]
                 getP: [a] "bc"
                       i = 0; i < 1:
                         newString = "bca"
                         newSet = []
                         getP: [] "bca"
                               print("bca");            ===>
              i = 2
       i = 2; i < 3:
         newString = "c"
         newSet = [a,b]
         getP: [a,b] "c"
               i = 0; i < 2:
                 newString = "ca"
                 newSet = [b]
                 getP: [b] "ca"
                       i = 0; i < 1:
                         newString = "cab"
                         newSet = []
                         getP: [] "cab"
                               print("cab")             ===>
                       i = 1
               i = 1; i < 2:
                 newString = "cb"
                 newSet = [a]
                 getP: [a] "cb"
                       i = 0; i < 1:
                         newString = "cba"
                         newSet = []
                         getP: [] "cba"
                               print("cba")             ===>
                       i = 1
               i = 2
        i = 3



*/