Пасьянс со стеком

[fregimus]

У меня возникла комбинаторная задачка со стековой машиной, которую было бы интересно проанализировать.

Представьте себе игру с перекладыванием карточек, целью которой является переставить карточки с буквами из исходного порядка в заданный. На каждой карточке написана или буква алфавита, или стрелка ↑. Правила перестановки букв таковы. Первоначально карточки с буквами и стрелкой выложены в ряд и берутся по одной слева направо. Если на карточке буква, то карточка кладется в стопку (если стопка пуста, то карточка будет в ней единственной, а если там уже есть карточки, то очередная карточка кладется поверх предыдущих). Если же на карточке стрелка, то эта карточка выбрасывается, а верхняя карточка из стопки выкладывается в отдельную строку для результата. Рассмотрим пример. Пусть задана последовательность карточек

О Р ↑ ↑ К ↑

Берем карточки слева направо по одной. Карточка О кладется в стопку, Р поверх нее. Затем первая стрелка велит выложить верхнюю карточку Р на выход, а вторая выкладывает (теперь верхнюю) О. Затем К кладется в стопку и следом, по команде последней стрелки, выкладывается на выход за первыми двумя. В результате получаем на выходе

Р О К

Вопрос задачи состоит в следующем. Пусть нам даны исходная строка (в нашем примере это ОРК) и предположительная выходная (РОК). Можно ли так разложить карточки-команды со стрелкой между буквами исходной строки, чтобы на выходе получилась заданная? Буквы в строке не обязательно все различные, например, А Н А Н А С — допустимая строка.

Можете легко проверить, что из строки А Б В можно получить только 5 из 6 возможных перестановок, а перестановку В А Б получить невозможно.

А ↑ Б ↑ В ↑ → А Б В
А ↑ Б В ↑ ↑ → А В Б
А Б ↑ ↑ В ↑ → Б А В
А Б ↑ В ↑ ↑ → Б В А
А Б В ↑ ↑ ↑ → В Б А

Предпочтительно конструктивное решение (т. е. правило расстановки), и, конечно, самое простое. Существует очевидное решение «в лоб»: будем расставлять n стрелок, где n длина строки, в любом возможном порядке, и проверять, получится ли на выходе искомая строка. Но нам придется перебрать n! возможных комбинаций — громадное число даже для 10 букв, так что такое решение не годится. Есть очень простое линейное в n решение для строки с различающимися буквами, но оно не работает, если разрешить повторы одинаковых букв в строке. А дальше ваш ход.

Доб. Наврал я с линейным решением — нашел контрпример.

Comments

[fregimus.livejournal.com]

Двигаться можно в любую сторону. Я с конца двигаюсь. Это алгоритм преобразования строки работает слева направо, а вопрос в задаче — можно ли преобразовать строку 1 в строку 2 — можно с любого конца решать. Наверное, я как-то не сфокусировал внимание на этом.

[fat-crocodile.livejournal.com]

это я неясно написал
я не имел ввиду, что Вы поставили такое ограничение, я имел ввиду, что
- не думал всерьёз о других способах решения -- просто потому что всерьёз над задачей не думал
- но среди алгоритмов, двигающихся по строке от начала к концу этот выглядит оптимальным. От конца к началу скорее всего тоже, наверняка там всё симметрично.

То есть остаются алгоритмы, не двигающиеся по строке, а как-то совсем иначе. Например, как написали ниже, что-нибудь с динамическим программированием и парами символов.

[fregimus.livejournal.com]

Нашел пример, который обманывает мое линейное якобы решение. Плохо дело…

[fat-crocodile.livejournal.com]

Для случая без повторов букв?
Покажите? Я просто пока не вижу разницы между любыми различными примерами, если буквы не повторяются, алгоритм совсем в лоб работает.

Или в общем виде? Но в общем Вы вроде на линейность и не претендовали.