N people (<13) stand in a line. I need to find the number of permutations when P people see everything on the left and R see everything on the right. That is, if N = 10, P = 4, R = 4, then "7 8 9 10 1 2 6 5 4 3" is the correct permutation.
I tried to implement a backtracking algorithm. However, the output is always 0. I check the conditions that clearly say that this path will not lead to a solution. For example, if a [0] = 10, then it makes no sense to iterate over the remaining i, since the leftmost person is the tallest and he closes the view. Here is my code:
public class Backtracking {
private static final int n = 10;
private static final int left = 4;
private static final int right = 4;
static int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
static int was[] = new int[10];
static int [] conditions = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
static int count = 0;
public static void main(String[] args) {
backtrack(0);
System.out.println(count);
}
private static void backtrack(int i) {
if(i > n) {
count++;
return;
}
for(int j = 0; j < n; j++) {
if(was[j] == 0) {
arr[i] = j;
was[j] = 1;
if(checkCondition(i)) {
backtrack(i + 1);
was[j] = 0;
}
}
}
}
private static boolean checkCondition(int i) {
if(i < left-1) {
int constrain = left-i;
if(arr[i] >= conditions[conditions.length - constrain]) {
return false;
}
}
else if (i > arr.length - right) {
int constrain = arr.length-i;
if(arr[i] >= conditions[conditions.length - constrain]) {
return false;
}
}
else {
if(arr[i] > arr[left-1] || arr[i] > arr[arr.length - right - 1]) {
return false;
}
}
return true;
}
}
UPD: Changed code and now all works fine (but for n = 13 it takes really much time):
public class Backtracking {
private static int n ;
private static int left;
private static int right;
static int arr[];
static int was[];
static int count = 0;
public static void main(String[] args) throws FileNotFoundException {
long start = System.currentTimeMillis();
Scanner scanner = new Scanner(new File("data/file.txt"));
int inputs = scanner.nextInt();
for(int i = 0; i < inputs; i++) {
count = 0;
n = scanner.nextInt();
left = scanner.nextInt();
right = scanner.nextInt();
arr = new int[n];
was = new int[n];
backtrack(0);
System.out.println(count);
}
long finish = System.currentTimeMillis();
long elapsed = finish - start;
System.out.println("Прошло времени, с: " + (double)elapsed / 1000.0);
}
private static void backtrack(int i) {
if(i > n - 1) {
count++;
return;
}
for(int j = 0; j < n; j++) {
if(was[j] == 0) {
arr[i] = j + 1;
was[j] = 1;
if(checkCondition(i)) {
backtrack(i + 1);
}
was[j] = 0;
}
}
}
private static boolean checkCondition(int i) {
/*
if(i < left-1) {
int constrain = left-i-1;
if(arr[i] >= conditions[conditions.length - constrain]) {
return false;
}
}
*/
if(i == n-1) {
if (countLeft(i) != left || countRight(i) != right) return false;
}
return true;
}
private static int countLeft(int n){
int count = 0;
for(int i = 0; i <= n; i++) {
boolean flag = false;
for(int j = 0; j < i; j++) {
if(arr[i] < arr[j]) {
flag = true;
break;
}
}
count = (flag) ? count : count + 1;
}
return count;
}
private static int countRight(int n) {
int count = 0;
for(int i = arr.length-1; i >= 0; i--) {
boolean flag = false;
for(int j = arr.length-1; j > i; j--) {
if(arr[i] < arr[j]) {
flag = true;
break;
}
}
count = (flag) ? count : count + 1;
}
return count;
}
}
Even though you observed the shortcut due to the position of the tallest person, the backtracking solution still bruteforces through too many possibilities. No surprise it takes too long. Think combinatorially.
P and N-R).Now, if the tallest person is in the position k, there are (n-1) chose (k-1) ways to populate the left partition. Assuming that a one-way-viewing problem admits F(p, k) solutions, an answer to the main problem is
sum[k: P..N-R] chose(n-1,k-1) F(P-1, k-1) * F(N-k-1, n-k)
To compute F(p, k), follow the same line. Fix the position j of the tallest person (it should be between p-1 and k). There are (k-1) chose (p-1) way to populate the left partition (and again, it doesn't matter who is selected); and the right partition could be in any order. An answer to the subproblem is given by a recursion
F(p, k) = sum[j: p-1..k] chose(j-1,k-1] (k-j)! F(p-1, j-1)
Now a straightforward memoization should give a result in a reasonable time.