Рекурсия vs мозг

Рекурсивная генерация комбинаторных объектов довольна удобна и часто позволяет быстро решить задачу. Однако у этого подхода есть несколько недостатков. При использовании рекурсивных генераторов при большой глубине рекурсии довольно сильно просаживается производительность. Эту проблему можно частично обойти, если не использовать генераторы, а использовать рекурсивную функцию, одним из параметров которой является префикс или суффикс собираемой последовательности. Это позволяет ускорить код в несколько раз, но результат несколько менее нагляден. Другая фундаментальная проблема заключается в том, что рекурсивно мы можем перебрать только все объекты в определённом порядке. По данной последовательности нет никакого «дешёвого» способа найти предыдущую или следующую, либо перескочить в процессе работы к некоторой определённой последовательности. Такая необходимость может возникнуть при оптимизации больших переборов: иногда становится понятно, что целую ветку последовательностей можно откинуть.

Поэтому в этом листке будет реализован другой подход к перебору комбинаторных объектов. Решение каждой задачи будет состоять из двух частей:

  1. Построение первого в заданном порядке объекта;
  2. Для любого данного объекта построение следующего за ним объекта.

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

Все задачи на перебор комбинаторных объектов должны решаться при помощи нерекурсивного генератора (или нерекурсивной функции в C++). Во всех задачах, предполагающих этот перебор использовать, можно пользоваться рекурсивными решениями из предыдущего листка.

Замечание по вводу-выводу

Следует иметь в виду, что во всех высокоуровневых языках программирования для большинства простых вещей есть пяток разных решений, производительность которых может отличаться на несколько порядков. Одной из таких вещей является вывод списков в Python. Вот самый простой и наивный способ выводить последовательности списков чисел:
for row in some_iterator:
    for i in range(len(row)):
        print(row[i], end=" ")
    print()
Вот другой способ, очень короткий и удобный, но очень медленный для больших списков:
for row in some_iterator:
    print(*row)
Эти способы могут быть в тысячи раз медленнее (при большом объёме данных), чем такой способ:
for row in some_iterator:
    print(' '.join(map(str, row)))
Поэтому если вы пишите вывод на олимпиаде, то первые два варианта лучше не использовать.

При некоторой ловкости можно сделать вывод такого сорта в одну строчку, используя '\n'.join, map, lambda, немного магии и функционального программирования. Кто сумеет придумать, как?

Упражнения

A: Двоичные последовательности

По данному натуральному n⩽15 выведите все двоичные последовательности длины n в лексикографическом порядке.

3
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

B: Потратить все деньги

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

В первой строчке даны натуральные числа S, количество денег у Вовочки, и K — количество булочек в кондитерской. В следующей строчки перечислены стоимости каждой булочки.

Если Вовочка может потратить все деньги, то выведите через пробел номера булочек, которые он при этом купит (выведите любой способ). Если же это ему никак не удастся, то выведите слово Impossible.

100 10 5 15 25 35 45 55 65 75 85 95
0 9
101 10 5 15 25 35 45 55 65 75 85 95
Impossible

C: Двоичные последовательности в обратном порядке

По данному натуральному n⩽15 выведите все двоичные последовательности длины n в обратном лексикографическом порядке.

3
1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0

D: Двоичные последовательности без двух единиц подряд в обратном лексикографическом порядке

По данному натуральному n⩽20 выведите все двоичные последовательности длины n, не содержащие двух единиц подряд, в обратном лексикографическом порядке.

3
1 0 1 1 0 0 0 1 0 0 0 1 0 0 0
Подсказка
Да, мне кажется, что я уже достаточно думал над этой задачей
Чес-слово! :)

Ясно, что самая первая последовательность имеет вид [1, 0, 1, 0, ...]. Теперь для того, чтобы найти следующую последовательность, нужно найти самую правую единицу. Начиная с неё хвост последовательности имеет вид [1, 0, 0, 0, ...], его нужно заменить на [0, 1, 0, 1, ...].

Последней последовательностью будет [0, 0, 0, 0, ...]. Для того, чтобы упростить поиск момента, когда пора остановиться, можно добавить в начало последовательности «бонусные» [1, 0]. Тогда нужно yield'ить последовательности (вернее срезы [2:]) только пока нулевой элемент последовательности равен 1.

E: Вовочка берётся за ум

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

В первой строчке дано натуральное число K — количество дней. Во второй строчке даны K целых чисел — ценности лекций для Вовочки (некоторые лекции он считает вредными). Выведите в порядке возрастания номера дней, в которые лучше всего слушать лекции Вовочке.

3 100 150 70
0 2
5 -10 100 130 20 -10
2

F: Двоичные последовательности длины n содержащие k единиц

По данным натуральным n и k (0⩽kn, n⩾1) выведите все двоичные последовательности длины n, содержащие ровно k единиц в лексикографическом порядке.

4 2
0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0
Подсказка
Думал-думал, не придумал :(
Подсказки «меняй 01..10..0 на 10..01..1», увы, недостаточно

Ясно, что самая первая последовательность — [0, ..., 0, 1, ..., 1]. В каком случае s-й член последовательности можно увеличить, не меняя предыдущие? Когда после s-го члена есть 1, которую для баланса мы заменим на 0. То есть нужно найти самый правый 0, за которым стоят единицы. В этом случае хвост последовательности имеет вид [0, 1, ..., 1, 0, ..., 0] (пусть там i единиц, i>0). Если мы заменим s-й член на 1, то оставшийся хвост нужно заменить на лексикографически минимальную последовательность, в которой i-1 единица, то есть [0, 1, ..., 1, 0, ..., 0] заменяется на [1, 0, ..., 0, 1, ..., 1].

Как обычно, для того, чтобы упростить отлов момента, когда пора остановиться, добавим слева «виртуальный» [0]. Тогда нужно yield'ить последовательности (вернее срезы [1:]) только пока нулевой элемент последовательности равен 0.

G: Вовочка и поднабор с нулевой суммой

На курсе по алгоритмам Вовочке предлагалось решить следующую NP-полную задачу:

Даны N чисел. Можно ли среди них выбрать K так, чтобы их сумма равнялась нулю?

Решите её и вы.

В первой строчке даны натуральные числа N K. Во второй строчке даны N целых чисел. Выведите через пробел в порядке возрастания K номеров чисел, имеющих сумму 0. Если такого набора нет, то выведите слово Impossible.

3 2 100 -30 30
1 2
3 2 100 -30 -70
Impossible

H: Возрастающие последовательности в обратном порядке

По данным натуральным n и k (nk) выведите все возрастающие последовательности длины n, состоящие из чисел 1..k в обратном лексикографическом порядке.

3 5
3 4 5 2 4 5 2 3 5 2 3 4 1 4 5 1 3 5 1 3 4 1 2 5 1 2 4 1 2 3
Подсказка
Я буду ботать! Но что-то нет идей... :(
Я пытался! Не получается...

Как и раньше, начальная последовательность очевидна: это [k-n+1, ..., k-1, k]. В каком случае можно уменьшить на единицу s-ый элемент? Когда он хотя бы на 2 больше предыдущего, либо он начальный. Для обратного порядка нужно найти самый правый такой s. Пусть мы уменьшили s-ый элемент на единицу, что нужно написать в хвост? Лексикографически максимальную последовательность, то есть [k-n+p, ..., k-1, k].

Как и выше, для того, чтобы упростить критерий останова, добавим слева «фальшивые» [-2, 0]. Тогда нужно yield'ить последовательности (вернее срезы [2:]) только пока первый элемент последовательности равен 0.

I: Перестановки

Дано натуральное число n. Выведите всевозможные перестановки чисел от 1 до n в лексикографическом порядке.

3
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
Подсказка
Да-да, это какая-то жесть... Что так сложно?
Я не халтурщик, просто моя муза сегодня не в настроении...

Первой будет перестановка [1, 2, ..., n], последней — [n, n-1, ..., 1]. В каком случае s-ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из последующих членов. Мы должны найти самый правый такой s, если X — наша текущая последовательность, то x[s] < x[s+1] > x[s+2] > ... > x[n-1]. Значение x[s] нужно увеличить минимальным образом, то есть найти среди x[s+1]..x[n-1] наименьшее число, большее его. Поменяв x[s] с ним местами, останется расположить числа с номерам s+1..n-1 так, чтобы перестановка была наименьшей, то есть в возрастающем порядке. Это всё весьма облегчается тем, что элементы s+1..n-1 уже идут в убывающем порядке, поэтому хвост нужно склеить из правой части хвоста (той части, где элементы меньше x[s]) в обратном порядке, x[s], и левой части хвоста (той части, где элементы больше x[s]) тоже в обратном порядке.

Примерчик: пусть хвост начиная с x[s] такой: [5, 9, 8, 7, 3, 2, 1]. Минимальный элемент, больший 5 — это 7. Поэтому новый хвост будет [7] + [3, 2, 1][::-1] + [5] + [9, 8][::-1], то есть [7, 1, 2, 3, 5, 8, 9].

И снова для того, чтобы упростить поиск момента для остановки, добавим слева «искусственный» [0]. Тогда нужно yield'ить последовательности (вернее срезы [1:]) только пока нулевой элемент последовательности равен 0.

J: Вовочка и задача коммивояжёра

Следующим шагом для продолжения обучения Вовочка решил выбрать для себя лучший университет. Он собрал список из N + 1 лучшего университета (университет в городе Вовочки имеет номер 0). На страничке awesome-python он нашёл ссылку на пакет robobrowser, при помощи которого с известного сайта добыл стоимости перелётов из города с i-м университетом в город с j-м университетом для всех i и j.

Вовочка хочет найти самый дешёвый круговой маршрут для посещения всех ВУЗов.

В первой строчки дано число N --- число университетов, не считая университета в родном городе Вовочке. В следующих N + 1 строках дана таблица с ценами перелётов из города с i-м университетом в город с j-м. Выведите в первой строчке минимальную стоимость перелётов, а во второй — любую из последовательностей перелётов с минимальной стоимостью.

3 0 8000 6500 8000 8000 0 2000 1500 8000 1500 0 2000 6500 2000 2000 0
16000 0 2 1 3 0

K: Расстановки ферзей

Известно, что на шахматной доске размером 8×8 можно расставить 8 ферзей не бьющих друг друга, причем сделать это можно 92 способами.

Дано натуральное n⩽8. Определите сколькими способами на доске n×n можно расставить n мирных ферзей.

8
92

L: Разбиение на невозрастающие слагаемые в обратном порядке

Дано натуральное число n. Выведите всевозможные его разбиения на слагаемые, упорядоченные в порядке невозрастания. Сами разбиения необходимо выводить в обратном лексикографическом порядке.

5
5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1
Подсказка
Эта задача вроде и простая, но что-то не получается... :(
Хотя я и думал на ней минут 30, не меньше...

Итак, нужно последовательно перебрать все разбиения начиная с [n], заканчивая [1, 1, ..., 1]. Каждым шагом уменьшать нужно первый справа член, не равный 1; найдя его, уменьшим на 1, а следующие возьмём максимально возможными: равными ему, пока хватает суммы, а последний — сколько останется.

Здесь для того, чтобы упростить поиск момента для остановки, добавим слева «флаг» [2]. Тогда нужно yield'ить последовательности (вернее срезы [1:]) только пока нулевой элемент последовательности равен 2.

M: Всё по i

Во время тура по университетам Вовочка обнаружил замечательную кондитерскую: «Всё по i». В ней для всех i от 1 до 30 были булочки за i долларов. Былая любовь к булочкам проснулась в нём, и он решил купить булочек на все оставшиеся S долларов.

В первой строчке дано натуральное число S — доступная Вовочке сумма денег. В следующей строчке даны min(S, 30) натуральных чисел — привлекательность булочек каждой стоимости для Вовочки.

Выведите любой из лучших наборов булочек, которые можно купить за S долларов.

10 1 1 2 3 3 4 9 7 8 9
7 1 1 1

N: Следующее слово

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

aab aba baa aaa
aba baa aab aaa

O: Правильные скобочные последовательности

Дано натуральное числo n. Выведите все правильные скобочные последовательности, состоящие из n открывающихся круглых скобок и n закрывающихся скобок в лексикографическом порядке.

3
((())) (()()) (())() ()(()) ()()()
Подсказка
Да вы издеваетесь, я уже голову сломал...
Правда-правда :)

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

Осталось научиться искать эту самую позицию первого изменения. Для этого будем идти по строке справа налево и подсчитывать баланс depth открытых и закрытых скобок (при встрече открывающей скобки будем уменьшать depth, а при закрывающей — увеличивать). Если в какой-то момент мы стоим на открывающей скобке, а баланс после обработки этого символа больше нуля, то мы нашли самую правую позицию, от которой мы можем начать изменять последовательность (в самом деле, depth > 0 означает, что слева имеется не закрытая ещё скобка). Поставим в текущую позицию закрывающую скобку, затем максимально возможное количество открывающих скобок, а затем все оставшиеся закрывающие скобки, — ответ найден.

Если мы просмотрели всю строку и так и не нашли подходящую позицию, то текущая последовательность — последняя, и пора заземляться.

Коды Грея

Иногда бывает полезно перечислять объекты в таком порядке, чтобы каждый следующий минимально отличался от предыдущего. Например, это позволило бы во второй задаче при переходе к очередной последовательности не вычислять заново полную сумму, а получить её всего лишь одним арифметическим действием из предыдущей суммы. Это позволило бы ускорить перебор в разы.

В 4А томе книги The Art of Computer Programming известного американского математика и специалиста в области компьютерных наук Дональда Кнута, целиком посвящённой комбинаторным алгоритмам (вдумайтесь, 900 страниц, посвящённых теме этого листочка!), кодам Грея посвящено несколько десятков страниц.

Изначально код Грея предназначался для защиты от ложного срабатывания электромеханических переключателей. Сегодня коды Грея широко используются для упрощения выявления и исправления ошибок в системах связи, а также в формировании сигналов обратной связи в системах управления.

Пусть есть вращающаяся ось, и мы хотим поставить датчик угла поворота этой оси. Насадим на ось барабан и сделаем на нём несколько дорожек из белых и чёрных частей, а также установим по фотоэлементу на каждую дорожку: Датчик угла поворота По сигналам с фотоэлементов мы сможем понять, в какой половине, четвертушке, восьмушке и т.д. расположен угол поворота барабана. Эта идея имеет, однако, недостаток: в момент пересечения границ сразу нескольких фотоэлементов могут менять сигнал, и если эти изменения произойдут не совсем одновременно (а они так и произойдут, не сомневайтесь!), то на какое-то время показания фотоэлементов будут бессмысленными. Коды Грея позволяют избежать этой опасности. Сделаем так, чтобы на каждом шаге менялось показание лишь одного фотоэлемента: Датчик угла поворота

А вот картинка реального устройства
Датчик абсолютного угла поворота. Оптические щели расположены в соответствии с кодом Грея

P: Бинарный код Грея при помощи рекурсии

Бинарный код Грея можно определить многими эквивалентными способами. Например, если \(\Gamma_n\) обозначает бинарную последовательность Грея, состоящую из списков длины n, то можно определить \(\Gamma_n\) рекурсивно, с помощью следующих двух правил:
\(\Gamma_0\) пусто, \(\Gamma_{n+1}\) = \(0\Gamma_n\), \(1\Gamma_n^R\).
Здесь \(\Gamma_n^R\) — обозначает последовательность \(\Gamma_n\) в обратном порядке. Поскольку последняя строка в \(\Gamma_n\) эквивалентна первой строке в \(\Gamma_n^R\), ясно, что на каждом шаге \(\Gamma_{n+1}\) изменяется ровно один бит, если \(\Gamma_n\) обладает тем же свойством.

Дано число n. Выведите бинарный код Грея длины n при помощи рекурсивного генератора.

4
0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0
Подсказка
Туплю...
Гы-ы-ы-ы :(

Добавьте необязательный параметр в генератор — направление кода. По умолчанию направление обычное. Если же направление перевёрнутое, то нужно выдавать \(1\Gamma_{n-1}\), \(0\Gamma_{n-1}^R\)

Q: Бинарный код Грея при помощи битовых операций

Оказывается, бинарный код Грея можно получить буквально за 4 строчки кода при помощи цикла, функции bin и трёх битовых операций. Получится что-то в этом духе:

def gray_bin(n):
    for i in range(1 << n):
        cur = bin(mystical_code)[2:]
        cur = '0' * (n - len(cur)) + cur
        yield cur
4
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
Подсказка
Должно получиться короче, чем «mystical_code»
Три битовых операции...

Может быть тогда сразу плюсик поставить? >>:->

R: Бинарный код Грея без внутренних циклов

Коды Грея позволяют существенно ускорить решение задач на подобие задачи B: так как при переходе к следующей последовательности меняется ровно одно значение, то для вычисления новой суммы также требуется ровно одна арифметическая операция. Для применения в задаче 2 нам не нужна вся последовательность нулей и единиц, достаточно лишь получать индекс j и знак +1/-1: тогда к текущей сумме нужно будет прибавить j-й элемент массива, умноженный на знак.

Для эффективного перебора последовательностей Гидеоном Эрлихом (Gideon Ehrlich) в 1973 году предложен следующий поразительно эффективный алгоритм: он выполняет только пять операций присваивания и одну проверку завершения алгоритма между соседними выдачами.

Алгоритм Эрлиха:

  1. [Инициализация.] \(a_i = -1\) для \(i=0,\ldots,n-1\), \(f_i = i\) для \(i=0,\ldots,n\);
  2. [Проверка завершения.] Если \(f_0\ge n\), то завершить работу;
  3. [Выбор j.] Установить \(j = f_0\), \(f_0 = 0\), \(f_j = f_{j+1}\), \(f_{j+1} = j+1\);
  4. [Посещение.] Установить \(a_j = -a_j\) и выдать пару \(j, a_j\). Вернуться к п.2.

Почему это работает? Это хорошая задача. Рекомендую заинтересованным и олимпиадникам разобраться и сдать устно.

1
0 1
2
0 1 1 1 0 -1
3
0 1 1 1 0 -1 2 1 0 1 1 -1 0 -1

S: Потратить все деньги — 2

Решите задачу B при ограничениях \(n\le 21\).

100 10 5 15 25 35 45 55 65 75 85 95
0 9
101 10 5 15 25 35 45 55 65 75 85 95
Impossible

T: Перестановки смежными обменами

Коды Грея позволяют эффективно генерировать все последовательности из нулей и единиц длины n. Те же рассуждения применимы и к генерации перестановок. Простейшим возможным изменением перестановки является обмен соседних элементов. При этом возникает естественный вопрос «Можно ли обойти все перестановки, обменивая на каждом шаге местами только два соседних элемента?» Если можно, то программа обхода всех перестановок в целом зачастую будет проще и быстрее, поскольку будет требовать каждый раз вычисления только одного обмена вместо обработки всего нового массива заново (см. задачу 10). Хорошая новость: простой алгоритм позволяет сгенерировать все n! перестановок с помощью n!-1 смежных обменов. Кроме того, еще один смежный обмен возвращает нас в начальное состояние, так что мы получаем гамильтонов цикл, аналогичный бинарному коду Грея.

На вход даётся число n. Напишите генератор, который последовательно выдаёт все n! перестановок так, что соседние перестановки отличаются лишь обменом соседних элементов.

3
1 2 3 1 3 2 3 1 2 3 2 1 2 3 1 2 1 3
Подсказка
В такой задаче подсказку смотреть не стыдно!
И даже нужно :)

Идея заключается в том, чтобы взять такую последовательность для \(\{1,\ldots,n-1\}\) и вставить число n в каждую из перестановок всеми возможными способами. Например, если \(n=4\), то последовательность (123,132,312,321,231,213) при вставке 4 во все четыре возможные позиции приводит к следующим столбцам массива:

1234 1324 3124 3214 2314 2134
1243 1342 3142 3241 2341 2143
1423 1432 3412 3421 2431 2413
4123 4132 4312 4321 4231 4213
Теперь мы получаем искомую последовательность, читая первый столбец сверху вниз, второй — снизу вверх, третий — сверху вниз, ..., последний — снизу вверх: (1234,1243,1423,4123,4132,1432,1342,1324,3124,3142,..., 2143,2134). Для того, чтобы упростить генерацию этой последовательности, построим биекцию между множеством перестановок и множеством последовательностей \(y_0,\ldots,y_{n-1}\), в которых \(y_i\le i\). А именно каждой перестановки поставим в соответствие последовательность \(y_0,\ldots,y_{n-1}\), где \(y_i\) — количество чисел, меньших \(i+1\) и стоящих левее \(i+1\) в этой перестановке. Взаимную однозначность легко доказать по индукции: перестановка длины \(n\) получается из перестановки длины \(n-1\) добавлением числа \(n\), котором можно поставить в любое из \(n\) мест. При этом к сопоставляемой последовательности добавляется ещё один член, принимающий значения от 0 до \(n-1\), а предыдущие члены не меняются. При этом оказывается, что транспозиции двух соседних чисел в перестановке соответствует изменение на единицу ровно одного из членов сопоставляемой последовательности. Вот чему соответствуют перестановки, перечисленные выше:
0000 0010 0020 0120 0110 0100
0001 0011 0021 0121 0111 0101
0002 0012 0022 0122 0112 0102
0003 0013 0023 0123 0113 0103
Заметим при этом, что увеличение на единицу числа \(y_i\) ведёт к обмену числа \(i+1\) с левым соседом, а уменьшение — c правым. Будем для каждого i хранить текущую позицию числа i+1 в перестановке в списке positions, а также будем хранить направление изменения каждого из чисел \(y_i\) в списке directions. Изначально positions[i] = i и directions[i] = +1. Будем идти по списку \(y_i\) справа налево и пытаться изменить число \(y_i\) на значение directions[i]. В случае успеха мы делаем обмен числа \(i+1\) с соседом, соответствующим directions[i]. Иначе (если мы упёрлись в 0 или i), то мы меняем знак у directions[i] и делаем шаг налево (уменьшаем i на единицу).
Permutation: 1 2 3.4     inversions: 0 0 0 0     positions: 0 1 2 3     directions: +1 +1 +1 +1
Permutation: 1 2.4 3     inversions: 0 0 0 1     positions: 0 1 3 2     directions: +1 +1 +1 +1
Permutation: 1.4 2 3     inversions: 0 0 0 2     positions: 0 2 3 1     directions: +1 +1 +1 +1
Permutation: 4 1 2.3     inversions: 0 0 0 3     positions: 1 2 3 0     directions: +1 +1 +1 +1
Permutation: 4.1 3 2     inversions: 0 0 1 3     positions: 1 3 2 0     directions: +1 +1 +1 -1
Permutation: 1 4.3 2     inversions: 0 0 1 2     positions: 0 3 2 1     directions: +1 +1 +1 -1
Permutation: 1 3 4.2     inversions: 0 0 1 1     positions: 0 3 1 2     directions: +1 +1 +1 -1
Permutation: 1.3 2 4     inversions: 0 0 1 0     positions: 0 2 1 3     directions: +1 +1 +1 -1
Permutation: 3 1 2.4     inversions: 0 0 2 0     positions: 1 2 0 3     directions: +1 +1 +1 +1
Permutation: 3 1.4 2     inversions: 0 0 2 1     positions: 1 3 0 2     directions: +1 +1 +1 +1
Permutation: 3.4 1 2     inversions: 0 0 2 2     positions: 2 3 0 1     directions: +1 +1 +1 +1
Permutation: 4 3 1.2     inversions: 0 0 2 3     positions: 2 3 1 0     directions: +1 +1 +1 +1
Permutation: 4.3 2 1     inversions: 0 1 2 3     positions: 3 2 1 0     directions: +1 +1 -1 -1
Permutation: 3 4.2 1     inversions: 0 1 2 2     positions: 3 2 0 1     directions: +1 +1 -1 -1
Permutation: 3 2 4.1     inversions: 0 1 2 1     positions: 3 1 0 2     directions: +1 +1 -1 -1
Permutation: 3.2 1 4     inversions: 0 1 2 0     positions: 2 1 0 3     directions: +1 +1 -1 -1
Permutation: 2 3 1.4     inversions: 0 1 1 0     positions: 2 0 1 3     directions: +1 +1 -1 +1
Permutation: 2 3.4 1     inversions: 0 1 1 1     positions: 3 0 1 2     directions: +1 +1 -1 +1
Permutation: 2.4 3 1     inversions: 0 1 1 2     positions: 3 0 2 1     directions: +1 +1 -1 +1
Permutation: 4 2 3.1     inversions: 0 1 1 3     positions: 3 1 2 0     directions: +1 +1 -1 +1
Permutation: 4.2 1 3     inversions: 0 1 0 3     positions: 2 1 3 0     directions: +1 +1 -1 -1
Permutation: 2 4.1 3     inversions: 0 1 0 2     positions: 2 0 3 1     directions: +1 +1 -1 -1
Permutation: 2 1 4.3     inversions: 0 1 0 1     positions: 1 0 3 2     directions: +1 +1 -1 -1
Permutation: 2 1 3 4     inversions: 0 1 0 0     positions: 1 0 2 3     directions: +1 +1 -1 -1