Crude Permutations

import java.util.*;

public class Dynamic {

public int calls = 0;
public int depth = 0;

public HashMap<String,HashSet<String> > cache = new HashMap<>();
public boolean cacheCheck = true;

public HashSet<String> preIndexList(String preIndexChr, HashSet<String> list) {
        // insert preindex char 'preIndexChr' to each element in list
        //System.out.printf("Pre Indexing with %s lst = %s",preIndexChr,list) ;
        HashSet<String> nList = new HashSet<>();
        for(String ele : list) {
                nList.add(preIndexChr + ele);
        }
        return nList;
}

// Depth
public HashSet<String> perm(String s,int dpth) {
        if (dpth > depth) {
                depth = dpth;
                //System.out.printf("Depth %d\n",depth) ;
        }
        if (cacheCheck && cache.containsKey(s)) {
                return cache.get(s);
        }

        calls++;

        HashSet<String> slst =  new HashSet<>();

        if (s.length() == 1) {
                slst.add(s);
                cache.put(s,slst);
                return slst;
        }

        for(int i = 0; i < s.length(); i++) {

                String left = s.substring(0,1);
                String right = s.substring(1);
                slst.addAll(preIndexList(left,perm(right,dpth++)));
                s = right + left;
        }
        cache.put(s,slst);
        return slst;

}

public String buildString(int size) {
        char [] ch = new char[size];
        for(int i = 0; i < size; i++) {
                ch[i] =  (char)(65 + i);
        }
        return new String(ch);
}
public static void main(String [] args) {
        for(int i = 1; i < 10; i++) {
                Dynamic d = new Dynamic();
                String s = d.buildString(i );
                HashSet<String> r = d.perm(s,0);
                //    System.out.printf("Perm of '%s' size = %d (built with %d calls)\nLIST %s\n",s,r.size(),d.calls,r) ;
                //System.out.printf("Size of HashMap %d\n",d.cache.size()) ;
                //System.out.printf("Perm of '%s' size = %d (built with %d calls)\n",s,r.size(),d.calls) ;
                // number of Calls can be expressed as recurance relation.
                // Kn = n * Kn-1 +  1
                System.out.printf("'%s' string size = %d list size = %d calls %d  depth %d\n",s,s.length(),r.size(),d.calls,d.depth);
                //System.out.printf("LIST %s",r) ;
        }
}

}