?

Log in

No account? Create an account

Previous Entry | Next Entry

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

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

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

О Р ↑ ↑ К ↑

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

Р О К

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

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

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

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

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

Tags:

Comments

( 28 comments — Leave a comment )
fat_crocodile
Oct. 28th, 2011 08:22 am (UTC)
Кажется, несколько одинаковых букв добавляют только некоторый элемент перебора.
То есть нужно не просто найти подходящую букву и поставить после неё стрелочку, а попробовать варианты со всеми подходящими буквами.
fat_crocodile
Oct. 28th, 2011 08:26 am (UTC)
Ну, например, мы можем занумеровать все одинаковые буквы, будут не АНАНАС, а A1Н1A2Н2A3С. Получили строку с различными буквами. Пусть это был вход. Теперь перебираем все возможные перестановки номеров в выходе и каждую проверяем за линейное время. Перестановок номеров конечно тоже может быть не мало, на всё же значительно меньше, чем n!
fregimus
Oct. 28th, 2011 08:31 am (UTC)
Да, backtracking. Я так и сделал, но мне не нравится. Хочется аналитическое решение найти или показать, что лучшего нет.
fat_crocodile
Oct. 28th, 2011 10:06 am (UTC)
если двигаться по строке с начала к концу, я не вижу, что может быть быстрее. Разве что некий способ ранней диагностики с отбрасыванием вариантов.
другое дело, что можно двигаться от конца к началу, или вообще неким образом рассматривать строку как целое, и ставить сначала те стрелочки, которые не могут быть не поставлены, и потом это упростит отбор вариантов.
fregimus
Oct. 28th, 2011 10:37 am (UTC)
Двигаться можно в любую сторону. Я с конца двигаюсь. Это алгоритм преобразования строки работает слева направо, а вопрос в задаче — можно ли преобразовать строку 1 в строку 2 — можно с любого конца решать. Наверное, я как-то не сфокусировал внимание на этом.
fat_crocodile
Oct. 28th, 2011 10:44 am (UTC)
это я неясно написал
я не имел ввиду, что Вы поставили такое ограничение, я имел ввиду, что
- не думал всерьёз о других способах решения -- просто потому что всерьёз над задачей не думал
- но среди алгоритмов, двигающихся по строке от начала к концу этот выглядит оптимальным. От конца к началу скорее всего тоже, наверняка там всё симметрично.

То есть остаются алгоритмы, не двигающиеся по строке, а как-то совсем иначе. Например, как написали ниже, что-нибудь с динамическим программированием и парами символов.
fregimus
Oct. 28th, 2011 04:27 pm (UTC)
Нашел пример, который обманывает мое линейное якобы решение. Плохо дело…
fat_crocodile
Oct. 28th, 2011 10:39 pm (UTC)
Для случая без повторов букв?
Покажите? Я просто пока не вижу разницы между любыми различными примерами, если буквы не повторяются, алгоритм совсем в лоб работает.

Или в общем виде? Но в общем Вы вроде на линейность и не претендовали.
racoonbear
Oct. 28th, 2011 08:47 am (UTC)
Что-то смаллиановское, да?
fregimus
Oct. 28th, 2011 04:28 pm (UTC)
Хуже. Из жизни…
vitaliborovikov
Oct. 28th, 2011 08:49 am (UTC)
Эта задача в общем виде (без учета повторяющихся букв) рассмотрена в 4-м упражнении 1-го тома Кнута в главе 2.2.1.
fregimus
Oct. 28th, 2011 08:58 am (UTC)
Спасибо. Вагончики. В конце книги даже есть ответ. Смотреть не стал, буду дальше думать.
Исенбаев Владислав
Oct. 28th, 2011 09:07 am (UTC)
Есть решение за O(n^3), можно методом динамического программирования посчитать для каждой пары подстрок исходной и выходной строк посчитать, можно ли из первой получить вторую.
По этим данным легко восстановить и конструктцию.
fregimus
Oct. 28th, 2011 04:27 pm (UTC)
Попробую, спасибо.
slobin
Oct. 28th, 2011 07:20 pm (UTC)
Если я ничего не путаю, backtracking с меморизацией даёт результат строго не хуже, чем динамическое программирование. В процессе экспериментов выяснил, что "АБРАКАДАБРА" преобразуется в "РАБА БАРДАКА" тремя способами (пробел добавлен для красоты :-).

... Free As In Love ...

fregimus
Oct. 28th, 2011 09:25 pm (UTC)
Похоже. Что-то у меня от этого примера уже кора потрескивает. Я-то думал он простенький, дай, думаю, в ЖЖ напишу, домохозяйкам досуг скрашу. А оказалось, задачка-то вон какая!
slobin
Oct. 29th, 2011 12:38 am (UTC)
Дальнейшее -- не ответ, а попытки думать вслух. Думаю вслух: а что не так с линейным решением? Вроде бы прав fat_crocodile: перебор возникает, только если есть повторяющиеся буквы. А если их нет, то переборный алгоритм вырождается в линейный. У меня, по крайней мере, вырождается. Можно мне тоже контрпример показать, вдруг у нас разные алгоритмы?

Ну, точнее, линейный он, если перестановку задать традиционным способом как перестановку 1..n: если там, как в ваших примерах, буквы (которые можно сравнивать только на равенство), то он превращается в квадратичный просто потому, что единственный способ узнать, что буква А ушла на пятое место -- это досчитать до пяти.

... Где они лежат, где они висят, где их точка? ...

fregimus
Oct. 29th, 2011 02:23 am (UTC)
Хвосты строк равной длины должны быть одной и той же подстрокой, прочитываемой в разные стороны (длина хвоста однозначно определятся позицией последней буквы исходной строки в проверяемой), а головы, если оборвать эти хвосты, должны обладать тем же свойством. N шагов по одной строке и 2N по другой. Только с вашей абракадаброй не работает, даже если его дополнить бэктрекингом.

Edited at 2011-10-29 02:24 am (UTC)
slobin
Oct. 29th, 2011 02:59 am (UTC)
Пытаюсь понять, похож ли ваш алгоритм на мой, если его применять слева направо: у меня всё крутится вокруг ПЕРВОЙ буквы исходной строки. Идея такая: если первая буква попала на k-тое место в выходной строке, значит, к этому моменту из стека ушло ровно k букв, и он в этот момент стал пустым. Значит, попало в него тоже ровно k букв (и все они ушли). Значит, левее k находится "правильная" перестановка 2..k первых букв, а правее -- k+1..n последних. Правильность для наглядности проверяем рекурсивно, но там суммарное количество вызовов получается n, а накладные затраты на рекурсию можно, кажется, убрать изощрённым программированием (но я поленился). А если есть несколько разных кандидатов на позицию, куда попала первая буква, то вот тут-то перебор и взлетает.

Реализация этой идеи в виде кода здесь (питон и генераторы (генераторы ведь нужны, чтобы варианты генерировать, правильно? :-)). Собственно решение задачи -- функция (генератор) transform, а evaluate -- это просто такой юнит тест, она собственно применяет все эти стрелочки и выдаёт итоговую перестановку (всегда одну и ту же, искомую). Важно: то, что генерятся правильные перестановки, я проверяю тупо и в лоб, там ошибиться вроде негде, а вот то, что генерятся ВСЕ правильные, что этот алгоритм ничего не пропускает -- не проверяю вообще. Если я лажанулся, то здесь. Выдача на тестовом примере:

abr!a!!!cadab!!r!!!!a! (True, 'rababardaca')
abr!a!!ca!dab!!r!!a!!! (True, 'rababardaca')
abr!a!!cada!b!ra!!!!!! (True, 'rababardaca')

... Глупое, злое и одноразовое ...

fregimus
Oct. 29th, 2011 04:22 am (UTC)
Спасибо, я посмотрю завтра или в воскресенье. Сегодня много дел.
fregimus
Oct. 29th, 2011 02:58 am (UTC)
Я что-то ни одного решения не могу найти вручную.
Исенбаев Владислав
Oct. 29th, 2011 10:08 am (UTC)
Нет, backtracking'у мемоизация не поможет. Если ему скормить строки "ababab..ab" и "ababab..ac", он обойдет все возможные состояния стека, коих не меньше чем 2^(n/2)
fat_crocodile
Oct. 29th, 2011 02:03 pm (UTC)
ну, сначала можно вставить проверку на принципиальную получаемость одной строки из другой любыми перестановками.
Исенбаев Владислав
Oct. 29th, 2011 06:56 pm (UTC)
Даже с проверкой полиномиального времени не будет
fat_crocodile
Oct. 30th, 2011 07:29 am (UTC)
не будет. Но привести пример уже не так просто.
pingback_bot
Oct. 29th, 2011 11:40 am (UTC)
No title
User slobin referenced to your post from No title saying: [...] (True, 'rababardaca') abr!a!!cada!b!ra!!!!!! (True, 'rababardaca') (Это я пытаюсь решать задачку [...]
fat_crocodile
Oct. 29th, 2011 03:21 pm (UTC)
И всё-таки, за линейный алгоритм для случая без повторов. Я предлагаю такой:

начало:
- пустой стек
- индекс в строке входа на начале
- индекс в строке выхода на начале

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

Если дошли до конца строки, а в стеке что-то не то -- значит не судьба.
Я не вижу, где тут может вкрасться нелинейность. Как объяснить это не ссылаясь на моё хорошее зрение:

- на каждом шаге мы либо снимаем верхний элемент стека -- O(1)
- либо движемся вперёд O(n)
- но суммарных движений вперёд не может быть больше чем n

значит в сумме это что-то типа O(2n) -- линейное.
faceted_jacinth
Dec. 2nd, 2011 11:33 pm (UTC)
У меня внезапно появилось время подумать про эту задачку.

Если все буковки различны, то есть два линейных алгоритма вычисления порядка пуш/попов, с начала и с конца. Оба со стеком, оба попают очередную буковку если она совпадает с вершиной стека. Прозреваю, что многих комментаторов смутили ваши стрелочки. Как можно оптимизировать их для ситуации с одинаковыми буковками -- не знаю. Особенно не знаю что делать если вообще все буковки одинаковы и решения нет.
( 28 comments — Leave a comment )