Нахождение всех перестановок тот ряд правил соответствия
Мне дают числа N, и для них применяют правила M об их порядке. Правила представлены в, пары индексов и каждая пара (A, B) говорит, что число с индексом A (Число A-th) должно быть ПОСЛЕ числа B-th - это не должно быть рядом с ним.
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.
Я попробовал bruteforcing, но он не работал (хотя "в лоб" должен работать в здесь, N находится в диапазоне (1,8).)
Какие-либо идеи?
3 ответа
Просто подсказка.
Вы можете рассматривать свой набор правил как график. Каждый индекс - это вершина, каждое правило - это направленное ребро.
Любой правильный порядок чисел (то есть перестановка, удовлетворяющая правилам) соответствует так называемому топологическому порядку приведенного выше графа. Чтобы сгенерировать все допустимые порядки номеров, вам необходимо сгенерировать все возможные топологические порядки этого графа.
P.S. Первый алгоритм топологического упорядочения, приведенный на связанной странице Википедии, уже позволяет получить довольно простое решение, которое перечислит все допустимые перестановки. Для его реализации потребуются определенные усилия и осторожность, но это не ракетостроение.
Грубое форсирование будет проходить через каждую перестановку , что составляет O (N!), И для каждой перестановки просто перебирать каждое правило чтобы подтвердить, что они aplpy, то есть O (M). В итоге получается O (N! M), что немного смешно, но это не должно «не работать» для такого маленького набора.
Честно говоря, лучше всего вернуться и заставить работать грубую силу. Как только это будет сделано (и если у вас еще есть время и т. Д.), Вы можете поискать лучший алгоритм.
ИЗМЕНИТЬ для голосующего против. Студент (должен быть) пытается выполнить домашнее задание вовремя . Судя по всему, его домашнее задание - это упражнение по программированию, где решение методом перебора было бы адекватным. Помощь ему в разработке эффективного алгоритма не решает его НАСТОЯЩУЮ проблему.
В этом случае он попробовал простой метод грубой силы (который, по общему мнению, должен работать для малых N значений), и преждевременно отказался от него, чтобы попробовать что-то более сложное. Любой опытный разработчик скажет вам, что это плохая идея.Студент нуждается в этом и заслуживает того, чтобы ему об этом сказали, и, если он рассудителен, он обратит внимание. Но очевидно, что это его выбор ...