Problem
number permutations with restrictions
Given the following 6 numbers 1, 2, 2, 3, 4, 5, write a main function, print out all the permutations that satisfy the limitations.
1. number 4 can not be at the third position from left.
2. 3 and 5 can not be the neighbors.
For example 512234, 412345.
Solution
It is a permutation problem with twists. For permutation problem, backtracing strategy is to branch at each position, only print out at the last position. Here, the constraints need to be applied.
- 3 and 5 can not be neighbors. We can modify the traceback routing by sending a flag to indicate a constraint is put by the previous position, so we have less choices for branching at current position.
- number 4 can not be at the third position from left. We can check it before printing the string.
- we have duplicate numbers, which can be removed by a Set datastructure.
import java.util.*;
public class PrintNumbers {
private Set<String> result = new HashSet<>();
//122345
public void perm(String str, boolean has4Or5, String remains) {
if(str.length() == 6) {
if(str.charAt(2) != '4') {
System.out.println(str);
result.add(str);
}
return;
}
for(int i = 0; i < remains.length(); i++) { //6
char c = remains.charAt(i); //1
if(has4Or5 && (c == '3' || c == '5'))
continue;
perm(str + c, (c == '3' || c == '5'), remains.substring(0, i) + remains.substring(i + 1));
}
}
public static void main(String...args) {
PrintNumbers pn = new PrintNumbers();
pn.perm("", false, "122345");
for(String word : pn.result) {
System.out.println(word);
}
System.out.println(pn.result.size()); //198
}
}
public class PrintNumbers {
private Set<String> result = new HashSet<>();
//122345
public void perm(String str, boolean has4Or5, String remains) {
if(str.length() == 6) {
if(str.charAt(2) != '4') {
System.out.println(str);
result.add(str);
}
return;
}
for(int i = 0; i < remains.length(); i++) { //6
char c = remains.charAt(i); //1
if(has4Or5 && (c == '3' || c == '5'))
continue;
perm(str + c, (c == '3' || c == '5'), remains.substring(0, i) + remains.substring(i + 1));
}
}
public static void main(String...args) {
PrintNumbers pn = new PrintNumbers();
pn.perm("", false, "122345");
for(String word : pn.result) {
System.out.println(word);
}
System.out.println(pn.result.size()); //198
}
}
We need to run the permutation, the cost is O(n!), the assumption is substring and string concatenation cost 1. The traceback need to hold the temporary strings in memory, the space cost has high bound O(n!), since java has a string pool, the cost in reality should be much lower.
Another approach is to view permutation problem as un-directed graph traversal. Each node is corresponding to a character. One node can lead to any other nodes except itself. Whenever there are constraints, we have to remove the corresponding edges. For example, remove edges between 3 and 5. The path during a dfs graph traversal for each node is the permutations. The constraints of number 4 can not be at the third position from left can be checked before printing. Duplicate can be removed with Set. The time cost and space cost is no better than the previous approach, but we listed here in order to give an alternative solution to make sure the answer is correct.
Time cost O(n!), space cost O(n!) but because of java string pool, this is an over estimate.
Another approach is to view permutation problem as un-directed graph traversal. Each node is corresponding to a character. One node can lead to any other nodes except itself. Whenever there are constraints, we have to remove the corresponding edges. For example, remove edges between 3 and 5. The path during a dfs graph traversal for each node is the permutations. The constraints of number 4 can not be at the third position from left can be checked before printing. Duplicate can be removed with Set. The time cost and space cost is no better than the previous approach, but we listed here in order to give an alternative solution to make sure the answer is correct.
import java.util.*;
public class PrintNumbers {
private Set<String> result2 = new HashSet<>();
private Set<Integer> visited = new HashSet<>();
private void graphTraversal() {
char[] chars = "122345".toCharArray();
int N = chars.length;
boolean[][] connected = new boolean[N][N];
//all connected
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(i != j) {
connected[i][j] = true;
}
}
}
//remove 3-5 edge
connected[3][5] = false;
connected[5][3] = false;
for(int i = 0; i < N; i++) {
visited = new HashSet<>();
dfs(connected, i, "122345".substring(i, i+1));
}
}
private void dfs(boolean[][] connected, int w, String path) {
visited.add(w);
if(path.length() == 6 && path.charAt(2) != '4') {
result2.add(path);
}
for(int v = 0; v < connected[w].length; v++) {
if(connected[w][v] && !visited.contains(v)) {
dfs(connected, v, path + "122345".substring(v, v+1));
visited.remove(v);
}
}
}
public static void main(String...args) {
PrintNumbers pn = new PrintNumbers();
pn.graphTraversal();
for(String word : pn.result2) {
System.out.println(word);
}
System.out.println(pn.result2.size()); //198
}
}
public class PrintNumbers {
private Set<String> result2 = new HashSet<>();
private Set<Integer> visited = new HashSet<>();
private void graphTraversal() {
char[] chars = "122345".toCharArray();
int N = chars.length;
boolean[][] connected = new boolean[N][N];
//all connected
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(i != j) {
connected[i][j] = true;
}
}
}
//remove 3-5 edge
connected[3][5] = false;
connected[5][3] = false;
for(int i = 0; i < N; i++) {
visited = new HashSet<>();
dfs(connected, i, "122345".substring(i, i+1));
}
}
private void dfs(boolean[][] connected, int w, String path) {
visited.add(w);
if(path.length() == 6 && path.charAt(2) != '4') {
result2.add(path);
}
for(int v = 0; v < connected[w].length; v++) {
if(connected[w][v] && !visited.contains(v)) {
dfs(connected, v, path + "122345".substring(v, v+1));
visited.remove(v);
}
}
}
public static void main(String...args) {
PrintNumbers pn = new PrintNumbers();
pn.graphTraversal();
for(String word : pn.result2) {
System.out.println(word);
}
System.out.println(pn.result2.size()); //198
}
}
Time cost O(n!), space cost O(n!) but because of java string pool, this is an over estimate.
Math
The number 198 is calculated this way:
a1 a2 a3 a4 a5 a6
3 constraints:
- a5 can not be at position 3.
- a4 and a6 can not be put together.
- a2 = a3.
The possible states without any constraint: 6!
reason: there are 6 choices for position 1, then 5 choices for position 2, then 4...
Apply constraint 1, a5 can not be at position 3.
I(total) = I(a5 is at position 3) + I(a5 is not at position 3)
I(total) = 6!
I(a5 is at position 3) = 5!
reason, a5 picked position 3, the rest of the 5 number chose 5 positions. The choices are 5!
As a result, after apply constraint 1, the total number of states that a5 can not be at position 3 is:
I(a5 is not at position 3) = 6! - 5! = 600.
Now additionally Apply constraint 2, a4 and a6 can not be put together.
We need to calculate number of states for (a5 is not at position 3) && (a4 a6 are not together).
I(a5 is not at position 3) = I(a5 is not at position 3 && a4 a6 are together) + I(a5 is not at position 3 && a4 a6 are not together)
I(a5 is not at position 3 && a4 a6 are together) is calculated this way:
We combine a4 a6 into one unit a46. Now the 6 elements permutation become 5 elements permutation. When we choose 5 of the possible start positions for combined element a46, there are 2 cases:
- the start position of a46 is 2 or 3
- the start position of a46 is not 2 or 3
I(a5 is not at position 3 && a4 a6 are together && the start position of a46 is 2 or 3) = 2 x 2 x 4!
reason: a4 and a6 are interchangeable, so we multiply 2, a45 can choose position 2 or 3, so we multiply another 2, finally, the since a4 or a6 hold the position 3, the rest of the 4 elements can chose any of the 4 positions left without any constraint, so we multiply 4!.
I(a5 is not at position 3 && a4 a6 are together && the start position of a46 is not 2 or 3) = 2 x 3 x 3 x 3!
reason: a4 and a6 are interchangeable, so we multiply 2, a45 can choose position 1, 4, 5, so we multiply 3. For the rest of the 4 elements choose the 4 positions left, a5 can not choose position 3, so it has 3 choices, so we multiply 3, for the rest of the 3 elements choose the rest of 3 positions left, there is no constraint, so we multiply 3!.
As a result,
I(a5 is not at position 3 && a4 a6 are not together) = I(a5 is not at position 3) - I(a5 is not at position 3 && a4 a6 are together) = 600 - (2x2x4! + 2x3x3x3!) = 396
Finally, we apply the constraint 3, a2 = a3.
I(a5 is not at position 3 && a4 a6 are not together && a2 = a3) = 396/2! = 198
reason: n of the elements are interchangeable, the n elements suppose to create n! different states, but now they only created 1 state, so we divide n! when apply the constraint.
