1234
1243
1324
1342
1324
1342
1423
1432
.
.
.
4321
In this case, we are going to use our same weapon, recursion. One of the best ways to understand recursion is to draw a tree to illustrate the logic. For the above example, we can draw the tree in the following way -

This is a partial tree, started only with 1. The complete tree has 3 more branches.
This is my solution -
public class Permutation {
final private int MAXN = 7;
private int[] flag = new int[MAXN];
private String input = null;
StringBuffer tempString = null;
/**
* Recursively generates all permutations.
*
* @param index
* @param level
*/
private void generatePermutation(int index, int level) {
tempString.setCharAt(level, input.charAt(index));
flag[index] = 1;
for (int i = 0; i < input.length(); i++) {
if (flag[i] == 0) {
generatePermutation(i, level + 1);
}
}
if (level == input.length() - 1) {
System.out.println(tempString);
}
flag[index] = 0;
}
/**
* Read Input from Standard Input.
*/
private void readInput() {
Scanner scanner = new Scanner(System.in);
this.input = scanner.nextLine();
if (this.input.length() > 7) {
System.exit(0);
}
this.tempString = new StringBuffer(this.input);
for (int i = 0; i < this.input.length(); i++) {
this.generatePermutation(i, 0);
}
scanner.close();
}
public static void main(String[] args) {
new Permutation().readInput();
}
}
This is a pretty easy solution if you master in backtracking.Well! can you modify the above program to generate unique permutations only? For an example, if you are given 112, then output should be-
112
121
211
Not like the above code produces:
112
121
112
121
211
211
As you see, there are some duplicate items are produced, which need to be removed. I am sure, you can do it.
No comments:
Post a Comment