A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. A string of length n has n! permutation.
Below are the permutations of string ABC.
ABC ACB BAC BCA CBA CAB
Solution based on backtacking:
Sample Program:
public class PermutationTest { public static void main(String[] args) { String str = "ABC"; int n = str.length(); PermutationTest permutation = new PermutationTest(); permutation.permute(str, 0, n-1); } private void permute(String str, int l, int r) { if (l == r) System.out.println(str); else { for (int i = l; i <= r; i++) { str = swap(str,l,i); permute(str, l+1, r); str = swap(str,l,i); } } }
public String swap(String a, int i, int j) { char temp; char[] charArray = a.toCharArray(); temp = charArray[i] ; charArray[i] = charArray[j]; charArray[j] = temp; return String.valueOf(charArray); }
}
Output:
ABC ACB BAC BCA CBA CAB
Time Complexity: O(n*n!) Note that there are n! permutations and it requires O(n) time to print a a permutation.
Note : The above solution prints duplicate permutations if there are repeating characters in input string.