Permutation of a string

On one of my job interviews I was asked to write a function that prints out all possible combinations of n characters for the given string. So, if the method is given the string "abc" as input, then it will print out the the following: "abc","acb","bac","bca","cab","cba".
Thanks to two years of studying statistics in university I knew that number of permutations in that kind of problem is calculated according the formula n in factorial, that is for case of 3 characters it is 3! -> 1*2*3 = 6, for case of 4 characters it is 4! -> 6*4 = 24. Unfortunately the knowledge of statistics and probability wasn't enough to help to solve the issue and after wasting all my time I had to admit that I don't have any solution. My interviewer was kind to me to explain me in really brilliant way the algorithm to solution of the problem. So I was so impressed, that immediately wrote the function when I returned from the interview. Now, here is the code I've written according to his algorithm:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

public void permute(String input) { permute("", input); } private void permute(String prefix, String word) { //System.out.println("start permute ("+prefix+","+word+")"); int n = word.length(); if (n == 0) { System.out.println(prefix); } for (int i = 0; i < n; i++) { permute(prefix + word.charAt(i), word.substring(0, i) + word.substring(i + 1, n)); } }

Input:

abc

Output:

abc

acb

bac

bca

cab

cba

Flow of recursive function permute(prefix, word)

Lets try to follow after what's happen here. The flow starts with the separation of input for two pieces a prefix and a word, when in beginning the prefix is an empty string and the word is the whole input.

Afterwards we start to call recursively the function permute when on every new call a new char is passed from word to prefix. The base case of this recursive function is when the word turn to be empty string then the function prints out a new permutation.

After returning from the base case the function return to for loop iteration, increases i and therefore selects a new character to be added to prefix.

The example of permute function's calls:

start permute (,abc)

start permute (a,bc)

start permute (ab,c)

start permute (abc,)  - base point and print

start permute (ac,b)

start permute (acb,) - base point

new iteration of loop when prefix is empty

start permute (b,ac) - and e.t.c.