Given a list of unique characters, generate or print out all permutations of characters.
For example:
input: [a, b, c]
output:
[a, b, c]
[b, a, c]
[c, b, a]
[a, c, b]
[b, c, a]
[c, a, b]
One of the permutation algorithm is done by swapping,
We have a list of permutations, which initially contains the input characters only.
Then we have two loops, outer loop (i) goes through index 0 to len-2, inner loop (j) goes from index i+1 to len-1, and for each current permutation, we generate one new by swap characters at i and j.
public static void permuIteratively(char[] chars){
assert chars!=null && chars.length>0;
List<char[]> result = new ArrayList<char[]>();
result.add(chars);
int len = chars.length;
/*
* the algorithm is doing swapping with two loops
* i: 0..len-2
* j: i+1..len-1
* for each string in the result list
* swap characters at i and j
* add swapping result string to the result
*
* since we can't change the list which iterating through list
* so we have to make a temp copy of the result and add swapping result
* into temp list
*
*/
for(int i=0; i<len-1; i++){
//make a copy of result
List<char[]> temp = new ArrayList<char[]>(result);
for(int j=i+1;j<len;j++){
//loop through result and swap i and j
for(char[] item : result){
char[] copy = Arrays.copyOf(item, item.length);
char tempC = copy[i];
copy[i] = copy[j];
copy[j] = tempC;
temp.add(copy);
}
}
result = temp;
}
for(char[] i : result){
System.out.println(Arrays.toString(i));
}
}
Once we find a way do it in iteratively, it is not difficutlt to switch to recursive way .
public static void permu(char[] chars){
List<char[]> l = new ArrayList<char[]>();
l.add(chars);
permuRec(chars, 0, l);
}
public static void permuRec(char[] chars, int index, List<char[]> current){
/*
* termination condition
*/
if(index==chars.length-1){
for(char[] i : current){
System.out.println(Arrays.toString(i));
}
return;
}
//make a copy of result
List<char[]> temp = new ArrayList<char[]>(current);
//then we grow the result by swapping
for(int j=index+1;j<chars.length;j++){
for(char[] item : current){
char[] copy = Arrays.copyOf(item, item.length);
char tempC = copy[index];
copy[index] = copy[j];
copy[j] = tempC;
temp.add(copy);
}
}
//continue on next index
permuRec(chars, index+1, temp);
}
Another way to do it is to by reduction. Basically we divide and conquer, find the permutations for substring start at i+1 first, then insert the character at i into all positions for each permutation from the subpromblem.
/**
* we solve this by reduction, for string s,
* first find the permutation of its substring from i+1
* then for each permutation, insert the character at i
* into all positions
*
* @param chars
*/
public static void permutationByDP(char[] chars){
System.out.println(permutationByReduRec(chars, 0));
}
public static List<List<Character>> permutationByReduRec(char[] chars, int index){
/*
* permutations are represented by list of characters
*/
List<List<Character>> result = new ArrayList<List<Character>>();
if(index == chars.length-1){
/**
* base case is the string only has one character
*/
List<Character> list = new ArrayList<Character>();
list.add(chars[index]);
result.add(list);
}
else{
/*
* we build the permutation by its substring index+1 first
*/
List<List<Character>> list = permutationByReduRec(chars, index+1);
char insert = chars[index];
for(List<Character> item : list){
/*
* then we insert char at index to all possible positions in the item
*/
for(int i=0; i<=item.size(); i++){
List<Character> copy = new ArrayList<Character>(item);
copy.add(i, insert);
result.add(copy);
}
}
}
return result;
}
No comments:
Post a Comment