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

Мне даны N чисел, и для них применяются правила M относительно их порядка. Правила представлены в парах индексов, и каждая пара (A, B) сообщает, что число с индексом A (A-th число) должно быть ПОСЛЕ 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.

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

Любые идеи?

Ответ 1

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

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

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

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

Ответ 2

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

Ответ 3

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

ИЗМЕНИТЬ нисходящему избирателю. Студент должен (должен) попытаться сделать домашнее задание вовремя. По его словам, его домашняя работа - это упражнение по программированию, в котором решение грубой силы было бы адекватным. Помогая ему разобраться в эффективном алгоритме, он не обращается к своей РЕАЛЬНОЙ проблеме.

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