Solution:
given abc.
We can ping a, then got the permutations of bc.
for bc, we can ping b, then find the permutations of c. {abc}
then we exchange bc, got cb, then ping c and find the permutations of b. {abc, acb}
now we can exchange a with b, got bac.
Then we ping b, repeat the above steps. {abc, acb, bac, bca}
then we exchange a with c, got cba.
Then we ping c, repeat the above steps. {abc, acb, bac, bca, cba, cab}
The formula is:
given string s, exchange ith character with first character, ping the first character, recursively find the permutations of the substring s.substring(1).
public class Permutations {
public static void printAllPermutations(String s) {
char[] str = s.toCharArray();
printAllPermutations(str, 0);
}
private static void exch(char[] s, int i, int j) {
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
}
private static void printAllPermutations(char[] str, int start) {
if(str == null || start < 0) {
return;
}
if(start == str.length - 1) {
System.out.println(str);
} else {
for(int i = start; i < str.length; i++) {
exch(str, start, i);
printAllPermutations(str, start + 1);
exch(str, start, i);
}
}
}
public static void main(String...args){
printAllPermutations("abc");
}
}
The time cost is O(N!) and space cost is O(1)
