(Untitled)

[rgu]

Наткнулся примерно месяц назад на http://rosalind.info/ на такую задачку.

Даны две перестановки чисел от 1 до n (n < 11). Перестановку разрешается изменять только выполняя т.н. развороты. Скажем, 1 4 5 2 6 3 можно поменять на 1 4 6 2 5 3

Comments

[aldanur]

BFS?

[rgu]

То ли я криво написал BFS, то ли ему плохо на таких объёмах (n = 10).

[aldanur]

Казалось бы, hashtable на 10! элементов и очередь на 9! элементов, из каждого выходит 45 рёбер, каждое посчитать за 10 -- типа 9!*10*45 на пять минут -- полмиллиона условных операций в секунду вроде может успеть...

[rgu]

Ну да, их там, правда, 5 пар и у меня питон.
В общем, мне кажется, я всё-таки налажал где-то. Проверю.