package com.anuragkapur.pie.recursion;

import java.util.ArrayList;
import java.util.List;

/**
 * @author anuragkapur
 */
public class Permutations {

    public List<String> getPermutations(String str) {

        if (str == null) {
            return null;
        }

        List<String> permutations = new ArrayList<>();
        if (str.length() == 1) {

            permutations.add(str);
        } else {

            char chars[] = str.toCharArray();
            for (int i = 0; i <chars.length; i++) {

                String prefix = String.valueOf(chars[i]);
                StringBuilder remainder = new StringBuilder();
                for (int j = 0; j <chars.length; j++) {
                    if (j != i) {
                        remainder.append(chars[j]);
                    }
                }

                List<String> subPermutations = getPermutations(remainder.toString());
                for (String subPerm : subPermutations) {
                    permutations.add(prefix+subPerm);
                }
            }
        }


        return permutations;
    }
}

@@ -212,152 +212,559 @@
     
-if (st
+PermutationsComputer permutationsCompute
 r =
-=
  n
-ull) %7B%0A            return null;%0A        %7D%0A%0A        List%3CString%3E permutations = new ArrayList%3C%3E();%0A        if (str.length() == 1) %7B%0A%0A
+ew PermutationsComputer(str);%0A        permutationsComputer.permute();%0A        return permutationsComputer.getPermutations();%0A    %7D%0A%0A    private class PermutationsComputer %7B%0A%0A        String input;%0A        boolean used%5B%5D;%0A        StringBuilder permutation;%0A        List%3CString%3E permutations;%0A%0A        public PermutationsComputer(String str) %7B%0A            if (str != null) %7B%0A                input = str;%0A                used = new boolean%5Bstr.length()%5D;%0A                permutation = new StringBuilder();%0A    
     
@@ -787,16 +787,27 @@
 ions
-.add(str
+ = new ArrayList%3C%3E(
 );%0A 
@@ -817,17 +817,13 @@
     
-%7D else %7B%0A
+    %7D
 %0A   
@@ -831,45 +831,43 @@
     
+%7D%0A%0A
     
-char chars%5B%5D = str.toCharArray();
+    public void permute() %7B%0A
 %0A   
@@ -879,169 +879,204 @@
     
+i
 f
-or
  (in
-t i = 0; i %3Cchars.length; i++) %7B%0A%0A                String prefix = String.valueOf(chars%5Bi%5D);%0A                StringBuilder remainder = new StringBuilder();
+put == null) %7B%0A                return;%0A            %7D%0A%0A            if (permutation.length() == input.length()) %7B%0A                permutations.add(permutation.toString());%0A            %7D else %7B
 %0A   
@@ -1101,33 +1101,36 @@
 int 
-j
+i
  = 0; 
-j %3Cchars
+i %3C input
 .length
+()
 ; 
-j
+i
 ++) 
@@ -1159,14 +1159,16 @@
 if (
-j != i
+!used%5Bi%5D
 ) %7B%0A
@@ -1195,33 +1195,42 @@
     
-remainder.append(chars%5Bj%5D
+permutation.append(input.charAt(i)
 );%0A 
@@ -1244,32 +1244,44 @@
             
-%7D%0A
     
-  
+used%5Bi%5D = true;%0A
           %7D%0A
@@ -1270,35 +1270,32 @@
 true;%0A          
-%7D%0A%0A
                 
@@ -1296,190 +1296,152 @@
     
-  List%3CString%3E subPermutations = getPermutations(remainder.toString());%0A                for (String subPerm : subPermutations) %7B%0A                    permutations.add(prefix+subPerm);
+permute();%0A                        used%5Bi%5D = false;%0A                        permutation.setLength(permutation.length()-1);%0A                    %7D
 %0A   
@@ -1480,17 +1480,68 @@
      %7D%0A%0A
-%0A
+        public List%3CString%3E getPermutations() %7B%0A    
         
@@ -1561,16 +1561,26 @@
 ations;%0A
+        %7D%0A
     %7D%0A%7D%0A

Refactor Permutations algo