Меняем фишки местами

[Xenia1996]

В ряд лежат фишки, на них написаны цифры 7, 8, 9, 4, 5, 6, 1, 2, 3.

Разрешается взять несколько лежащих подряд фишек и изменить их порядок на обратный.

За какое наименьшее число таких операций можно получить 1, 2, 3, 4, 5, 6, 7, 8, 9?

Приведите пример и докажите, что за меньшее число операций это сделать не удастся.

[zhekas]

за 3

[Xenia1996]

zhekas в сообщении #439308 писал(а):

за 3

А почему за 2 нельзя?

[maxal]

В общем случае эта задача называется "sorting by reversals". Она особенно важна для биоинформатики, хотя там обычно элементы имеют знаки и каждая reversal меняет знаки переставляемых элементов на противоположные.
Задача в беззнаковом случае является NP-полной, а в знаковом случае - полиномиально разрешимой.

Вот онлайновая тулза, которая решает эту задачу для заданных перестановок: http://grimm.ucsd.edu/GRIMM/

[Xenia1996]

maxal в сообщении #441038 писал(а):

В общем случае эта задача называется "sorting by reversals". Она особенно важна для биоинформатики, хотя там обычно элементы имеют знаки и каждая reversal меняет знаки переставляемых элементов на противоположные.
Задача в беззнаковом случае является NP-полной, а в знаковом случае - полиномиально разрешимой.

Вот онлайновая тулза, которая решает эту задачу для заданных перестановок: http://grimm.ucsd.edu/GRIMM/

Анечка смогла без "тулзы" доказать: http://e-science.ru/forum/index.php?showtopic=30368

(Оффтоп)

По поводу слова "тулза".
Теперь я понимаю, почему мы говорим "эскимосы"
Ведь "с" уже само по себе указывает на множественное число, а мы ещё и "ы" добавляем...