Сортировка стеком

Вагоны стоят на первом пути в каком-то порядке. Разрешено загонять вагоны с первого пути в тупик и вытаскивать их из тупика на второй путь. Обратно — нельзя. Требуется получить на втором пути вагоны в порядке $1, 2, \ldots, n$.

Тупик работает как стек: вагон, загнанный последним, выйдет первым. Значит, вопрос звучит так: какие перестановки сортируются одним стеком?

Почему жадность здесь не выбор, а необходимость

Обычно жадный алгоритм надо доказывать. Здесь доказывать нечего: на каждом шаге допустимо ровно одно осмысленное действие.

Пусть мы уже вывели вагоны $1, \ldots, k-1$ и ищем вагон $k$.

• Если $k$ лежит на вершине тупика — снимаем и выводим. Не сделать этого нельзя: пока $k$ не выведен, дальше двигаться некуда, а закопать его глубже мы не можем.
• Если $k$ ещё на первом пути — придётся загнать в тупик все вагоны до него включительно. Других способов добраться до $k$ нет.
• Если $k$ в тупике, но не на вершине — проиграли. Сверху лежит вагон с большим номером, он обязан выйти раньше, а нужен нам позже.

Выбора нет ни в одной ветке. Поэтому алгоритм, который просто следует этим правилам, либо приводит к цели, либо доказывает, что цели нет.

bool sortable(const vector<int>& a) {
    int n = a.size();
    vector<int> st;
    int need = 1, i = 0;
    while (need <= n) {
        if (!st.empty() && st.back() == need) { st.pop_back(); need++; continue; }
        if (i == n) return false;          // на первом пути пусто, а нужного нет
        st.push_back(a[i++]);
    }
    return true;
}

Каждый вагон входит в стек не более одного раза и выходит не более одного раза, поэтому $O(n)$ — несмотря на вложенный цикл. Это амортизированная оценка в чистом виде.

Проверено: на всех перестановках длины до восьми жадный алгоритм совпал с полным перебором состояний.

Критерий

Есть и локальное описание. Перестановка сортируется стеком тогда и только тогда, когда в ней нет образца 231 — то есть нет тройки индексов $i < j < k$ с $a_k < a_i < a_j$.

Смысл прямой: $a_i$ попадёт в стек раньше $a_j$ и окажется под ним, а вывести надо сначала $a_k$, потом $a_i$, потом $a_j$. Вагон $a_j$ лежит сверху и мешает.

Проверять критерий напрямую не нужно — симуляция и короче, и быстрее. Но он объясняет следующий факт.

Сколько таких перестановок

$n$	сортируемых	всего
1	1	1
2	2	2
3	5	6
4	14	24
5	42	120
6	132	720
7	429	5 040
8	1 430	40 320
9	4 862	362 880

Это в точности числа Каталана — те же, что считают правильные скобочные последовательности. Совпадение не случайное: последовательность действий со стеком — это и есть скобочная последовательность, где «загнать в тупик» — открывающая скобка, «вытащить» — закрывающая.

Соответствие взаимно однозначное, поэтому и количества совпадают. Посчитано перебором всех перестановок до девяти элементов.

Заодно это оценка, насколько задача жёсткая: доля сортируемых перестановок $C_n / n!$ падает экспоненциально. При $n = 9$ это уже 1,3%.

Вариации

Два стека или дек вместо одного стека. Класс сортируемых перестановок расширяется, критерий усложняется, а жадность перестаёт быть единственно возможной — появляется настоящий выбор, и задача становится содержательно другой.

Нужен не ответ «да/нет», а последовательность операций. Тот же алгоритм, только записываем каждое действие: push при загоне в тупик, pop при выводе. Длина протокола ровно $2n$.

Целевой порядок не $1 \ldots n$, а произвольный. Перенумеруйте вагоны так, чтобы целевой порядок стал возрастающим, и запустите то же самое.