Java Program to print all permutation of a String?

Interviewer may start with a very basic question as to what is number of permutations of a string with n characters. In case repetition is not allowed then it would be n!  i.e  [n*(n-1)*(n-2*....*!)]  . if repetition is allowed it would be n^n i.e [n*n*...n times].

Next would be to code it actually. Generally language is not a concern. What interviewer looks is how candidate thinks(his solving ability) and whether he is able to complete error free and working code. Following is a Java code that will print permutations of a given String along with the number of permutations possible.

Example :

Code : 

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 11/19/13
 * Time: 3:16 PM
 */
public class PermutationsPrinter {
    private int noOfPermutation;
    public void permute(char[] line,int start, int end){
        int j;
        if(start == end){
            noOfPermutation++;
            System.out.println(line);
        }
        else {
            for(j=start;j<=end;j++){
                char[] newLine = getSwappedString(line, start, j);
                permute(newLine,start+1,end);
            }
        }
    }


    private char[] getSwappedString(char[] characters,int i,int j ){
        String newLine = String.valueOf(swap(characters,i,j));//Create New String
        swap(characters,i,j);//restore original String
        return newLine.toCharArray();
    }


    private char[] swap(char[] characters,int i,int j){
        char temp = characters[i];
        characters[i] = characters[j];
        characters[j] = temp;
        return characters;
    }


    public int getNoOfPermutation() {
        return noOfPermutation;
    }


    public static void main(String args[]){
        String line = "ABC";
        PermutationsPrinter permuter = new PermutationsPrinter();
        permuter.permute(line.toCharArray(), 0, line.length() - 1);
        System.out.println("Number Of Permutations made : " + permuter.getNoOfPermutation());
    }
}

Output  : 

ABC

ACB

BAC

BCA

CBA

CAB

Number Of Permutations made : 6

(3! = 6 as expected)

More better example where you don't have to swap again to restore string is provided in the Interview questions git repo -

• Print All String Permuatation