Подсчитайте количество возможных перестановок чисел меньше целого числа N, заданных ограничений N-1

Question

Нам задано целое число N, и нам нужно подсчитать общее количество перестановок чисел меньше N. Нам также даны ограничения N-1. например:

, если N=4 затем подсчитать перестановки 0,1,2,3 данные:

0>1 
0>2 
0>3 

я подумал о том, чтобы график, а затем рассчитывают общее количество перестановок чисел на том же уровне и умножить его с перестановками в других level.eg :

для вышеприведенного примера:

   0 
     /| \ 
     /| \ 
     1 2 3 ------> 3!=6 So total no of permutations are 6. 

Но у меня есть трудности в его осуществлении в C++. Кроме того, этот вопрос был задан в кубке хакеров Facebook, конкурс закончился. Я видел код других людей и обнаружил, что они сделали это, используя DFS. Любая помощь?

Answer 1

Самый простой способ сделать это - использовать стандартный генератор перестановок и отфильтровать каждую перестановку, которая нарушает условия. Это, очевидно, очень неэффективно и для больших значений N не является вычислимым. Выполнение этого - это своего рода «болтливый» вариант, который есть у этих конкурсов, который позволяет менее умным участникам решить проблему.

Квалифицированный подход требует понимания способов подсчета комбинаций и перестановок. Чтобы проиллюстрировать метод, я буду использовать пример. Входы:

N = 7 
    2 < 4 
    0 < 3 
    3 < 6 

Сначала упростить это путем объединения зависимых условий в одно условие, а именно:

2 < 4 
    0 < 3 < 6 

Start с самым длинным состоянием, и определить количество комбинации из зазоров (это ключевое понимание). Например, некоторые из следующих комбинаций:

XXXX036 
    XXX0X36 
    XXX03X6 
    XXX036X 
    XX0XX36 
    etc. 

Теперь вы видите, что есть 4 пробела:? 0? 3? 6 & le;. Нам нужно подсчитать возможные разбиения X в этих четырех пробелах. Количество таких разделов равно (7 выберите 3) = 35 (вы видите, почему?). Теперь мы размножаемся следующими комбинациями следующего условия: 2 < 4 над оставшимися пустыми пятнами (Xs). Мы можем умножить, поскольку это условие полностью не зависит от состояния 0 6. Это количество комбинаций (4 выбирают 2) = 6. Окончательное условие имеет 2 значения в 2 пятнах = 2! = 2. Таким образом, ответ равен 35 х 6 х 2 = 420.

Теперь давайте сделаем это немного сложнее. Добавить условие:

1 < 6 

Как это изменит расчет, так это то, что до того, как 036 должно было появиться в этом порядке. Но теперь мы имеем три возможные меры:

1036 
    0136 
    0316 

Таким образом, общее количество теперь (7 выбирают 4) х 3 х 3 (выбрать 2) = 35 х 3 х 3 = 315.

Итак, повторим, процедура заключается в том, что вы изолируете проблему в независимых условиях. Для каждого независимого условия вы вычисляете комбинации разделов, затем вы умножаете их вместе.

Я прошел этот пример вручную, но вы можете запрограммировать ту же процедуру.