import java.util.*;

class Exercise2 {
	public static void main(String[] args) {
		for (String s: permute("catdog"))

		System.out.println(s);
	}

	public static ArrayList<String> permute(String letters) {

		ArrayList<String> perms = new ArrayList<String>();

		if (letters.length() == 1) {
			perms.add(letters);
		} else {

			for (int i=0; i<letters.length(); i++) {
				//choose a character out of the letters
				//So for "cat" this would be "c"
				char character = letters.charAt(i);

				//Grab remaining letters, i is excluded
				//So for "cat" this would be "at"
				String substring = letters.substring(0, i) + letters.substring(i+1);

				//Recursive
				//So it would permute("at")
				ArrayList<String> subperms = permute(substring);

				for (String tail : subperms) {
					perms.add(character + tail);
				}
			}
		}
		return perms;
	}
}