Блог

N человек (<13) стоят в очереди. Мне нужно найти количество перестановок, когда P людей видят все слева, а R видят все справа. То есть, если N = 10, P = 4, R = 4, то «7 8 9 10 1 2 6 5 4 3» это правильная перестановка.

Я попытался реализовать алгоритм обратного отслеживания. Однако результат всегда равен 0. Я проверяю условия, которые четко говорят, что этот путь не приведет к решению. Например, если a [0] = 10, то нет смысла перебирать оставшиеся i, так как крайний слева человек самый высокий, и он закрывает обзор. Вот мой код:

 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:
Изменен код, и теперь все работает нормально (но для n = 13 это занимает действительно много времени):

 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;
    }
}
 

Даже если вы заметили сокращение из-за положения самого высокого человека, решение с обратным отслеживанием по-прежнему использует слишком много возможностей. Неудивительно, что это занимает слишком много времени. Подумайте комбинаторно.

• Исправьте положение самого высокого человека (оно должно быть между P и N-R ).
• Обратите внимание, что для любого пользователя в левом разделе вид справа заблокирован. То же самое для правильного раздела. Проблема естественным образом разбивается на две проблемы с односторонним просмотром.
• Обратите внимание также, что не имеет значения, кто именно находится в левом разделе. Независимо от того, сколько перестановок. То же самое для правильного раздела.

Теперь, если на позиции находится самый высокий человек k , есть (n-1) chose (k-1) способы заполнить левый раздел. Предполагая, что проблема одностороннего просмотра допускает F(p, k) решения, ответ на основную проблему таков

 sum[k: P..N-R] chose(n-1,k-1) F(P-1, k-1) * F(N-k-1, n-k)
 

Для вычисления F(p, k) следуйте той же строке. Исправьте положение j самого высокого человека (оно должно быть между p-1 и k ). Есть (k-1) chose (p-1) способ заполнить левый раздел (и опять же, не имеет значения, кто выбран); и правый раздел может быть в любом порядке. Ответ на подзадачу дается рекурсией

 F(p, k) = sum[j: p-1..k] chose(j-1,k-1] (k-j)! F(p-1, j-1)
 

Теперь простое запоминание должно дать результат за разумное время.