Mad_08
Newbie | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору Господа, есть вопрос по следующей задаче: Имеется n-элементная перестановка, и m транспозиций (ai, bi). Требуется проверить могла ли она быть получена при помощи данных транспозиций и если да, то вывести каким способом. То что пришло мне в голову: в принципе можно было бы свести это дело к графу, а потом пройтись dfs-ом с отсечением по времени (заодно если может быть получена, то там сразу раскрутим по рекурсии и путь), но тут проблема в том, что 1<=n<=100, и я не могу придумать переход к графу, потому что если бы n было бы до 10, то тогда можно было бы просто занумеровать перестановки, но здесь... В общем вот так. Может быть есть какое-нибудь математическое решение? Очень надеюсь на вашу помощь! Add: Ещё немного подумал... А что если разбить перестановку на композицию независимых циклов типа (a b c)(d f), а затем по транспозициям как по рёбрам пройтись и посмотреть можно ли из a получить b, из b - c, и из d - f? Помоему это катит... но мало ли? Нет ли тут каких-нибудь подводных камней? | Всего записей: 1 | Зарегистр. 12-01-2008 | Отправлено: 06:44 12-01-2008 | Исправлено: Mad_08, 06:59 12-01-2008 |
|