Поиск всех перестановок, соответствующих набору правил

Question

Мне дано N номеров, и для них применяются М правил, касающихся их порядка.Правила представлены в парах индексов, и каждая пара (A, B) говорит, что число с индексом A (A-ое число) должно быть ПОСЛЕ B-го числа - оно не должно быть рядом с ним.

Ex: N = 4
    1 2 3 4
    M = 2
    3 2
    3 1

Output: 1234, 4213, 4123, 2134, 2143, 2413, 1423 ...Maybe there are even more:) 

Алгоритм должен дать мне все доступные перестановки, которые не нарушают правила, как в примере - 3 всегда должно быть после 2 и после 1.

Я пыталсябрутфорс, но это не сработало (хотя брутфорс должен работать здесь, N находится в диапазоне (1,8).)

Есть идеи?

Answer 1

Как подсказка.

Вы можете рассматривать ваш набор правил как график. Каждый индекс - это вершина, каждое правило - это направленное ребро.

Любое правильное упорядочение чисел (то есть перестановка, удовлетворяющая правилам) соответствует так называемому топологическому упорядочению приведенного выше графика. Чтобы сгенерировать все действительные порядки ваших чисел, вам нужно сгенерировать все возможные топологические порядки этого графа.

P.S. Первый алгоритм топологического упорядочения, приведенный на связанной странице Википедии, уже позволяет получить довольно простое решение, которое перечислит все допустимые перестановки. Это потребует некоторых усилий и некоторой осторожности, но это не ракетостроение.

Answer 2

Грубое принуждение будет проходить через каждую перестановку , что составляет O (N!), И для каждой перестановки просто циклично проходить через каждое правило, чтобы подтвердить, что они aplpy, то есть O (M). Это в конечном итоге O (N! M), что довольно смешно, но это не должно "не работать" для такого маленького набора.

Answer 3

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

РЕДАКТИРОВАТЬ вниз избирателя. Студент (должен быть) пытается выполнить свою домашнюю работу вовремя . Судя по всему, его домашнее задание - это упражнение по программированию, в котором было бы адекватным решение грубой силы. Помочь ему найти эффективный алгоритм - не решить его РЕАЛЬНУЮ проблему.

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