Кратчайшее введение в создание компилятора

«A compiler is a tool that translates software written in one language into
another language». (K. Cooper. L Torczon. Engineering a Compiler)

Т.е. достаточно sed, grep и awk и можно писать компилятор.

Вот бы кто-нибудь компилятор из PHP (для основных конструкций работы с массивами и строками) в С сделал.
А то мной было подмечно, что код из PHP перекладывается в С почти без усилий.

Иди-ка ты на !@# со своей «токсичностью»

Простите, а почему к сожалению, если с высшим образованием физмамта и мехмата не всегда возможно найти себе применение, кроме варианта остаться на кафедре?!
Мне казалось, что физмат дает очень хорошую фундаментальную базу, что в купе с выработанной аккуратностью и собранностью и т.д. делает из человека хорошего программиста (сужу со стороны, сам я филолог). Конечно, наверное, в понимании физика уход из физики в чистое программирование — это движение вниз.

Иди-ка ты на !@# со своей «токсичностью»

Раз не попал ты на ФизМат,
То пойдешь в айтишный детский сад (С).

Сортировка «Ханойская башня»

Он мне тоже объяснял некоторые вещи. Светлая помять

Как я делал комикс-игру по Лавкрафту

Вообще думал о самом концепте комикс-игры и понял, что это до не которой степени спасение тонущий игровой индустрии. От 3D многие устали уже 10 лет назад. От чистых текстовых игр тоже подустали. Комикс-игры, если еще соединить с мультиплеером (+ чат, форум, взаимодействие игроков) — промежуточный вариант между текстовой MMORPG и квест, но с упором на работу художника — очень даже очень путь… Вторая картинка волну Хокусая напомнила.

Загадочный математический гений и писатель продвигают решение задачи о перестановке

Я не специально прятал. Вываливал все как есть. Не хотелось вникать, как github устроен.
Я тоже думал про то, что считать можно только до половины. Далее пройтись по выводу с конца к началу.
Алгоритм на Ruby похоже считает сумму и выводит только часть строки.

Загадочный математический гений и писатель продвигают решение задачи о перестановке

Я выводил как-то свой первый алгоритм, там делал именно с проверкой больше меньше: github.com/dcc0/permutations/blob/master/.gitignore/permutations_first_script.c
Но там другой порядок вывода, а он не подойдет для создания последовательности. Рекурсивный на Ruby хочу разобрать.

Загадочный математический гений и писатель продвигают решение задачи о перестановке

Если на строке или массиве возрастающий порядок (а в этом случае это именно так), т.е.
12345, то последняя перестановка — это реверс от первой. Т.е. 54321. По ней и можно делать остановку.
т.е. пока ( строка != «54321» ). Но каждый раз сравнивать строки, наверное, не очень хорошо. strcmp вроде бы посимвольно сравнивает. Потеря времени. Вариант с факториалом (субъективно) выглядит более строго в математическом смысле. Такой алгоритм легче понять и перевести на псевдокод или любой язык. Его уже можно воткнуть в курсовую или статью.

Загадочный математический гений и писатель продвигают решение задачи о перестановке

Я делал так: abсdefghij
Даже если не использовать массивы, в распоряжении 120 с хвостом символов аски.

Упорядочил исходный алгоритм на С89 на stdio.
github.com/dcc0/permutations/blob/master/permutations_spiral.c

Загадочный математический гений и писатель продвигают решение задачи о перестановке

Только, наверное, есть ограничения на длину результатирующей строки. Т.е. при практическом применении нужно периодически сбрасывать строку в файл и очищать переменную, но это уже частный вопрос. Не часть самого алгоритма.
Про рекурсивный вариант, нашел на Ruby.
https://rosettacode.org/wiki/Superpermutation_minimisation#Ruby

Загадочный математический гений и писатель продвигают решение задачи о перестановке

Выдаст какой-то результат, но в контексте работы со строками последнее число в строке 12345678910 — это два числа. Достаточно задать значения в массив и будет работать корректно. Только substr надо будет на array_splice переписать и strrev на array_reverse, но разрезку и оборот части строки можно по-другому выразить.

Загадочный математический гений и писатель продвигают решение задачи о перестановке

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

<?php
$n = 7;
$fact = 5040;
$perm = "1234567";
for ($i = 1; $i != $fact + 1; $i++)
	{
	print $perm . "\n";
	$mm = $i;
	$m = $n;
	while ($m > 0)
		{
		if ($mm % $m == 0) {
			$mm/= $m--;
			}
		  else
			{
			$perm = substr($perm, $n - $m + 1).strrev(substr($perm, 0, $n - $m + 1));
			continue 2;
			}
		}
	}
?>

Загадочный математический гений и писатель продвигают решение задачи о перестановке

Да. Вы были правы. Циклический сдвиг не нужен. Он и так получается разрезкой строки и разворотом первой части

Как я делал комикс-игру по Лавкрафту

Графический стиль очень привлекательный.

Загадочный математический гений и писатель продвигают решение задачи о перестановке

Наверное, вы правы.
Сделал, последовательность у меня без последней единицы. Для n = 10 получилось 4979527

github.com/dcc0/Superpermutations_php/blob/master/superpermutations.php

Загадочный математический гений и писатель продвигают решение задачи о перестановке

Я имею в виду, что, похоже, сама генерация перестановок с этим кодом быстрее, чем генерация перестановок на php другими алгоритмами. Нет сомнений, что на С++ быстрее. Но мне на С и С++ неудобно черновой алгоритмизацией заниматься. Проверю ваш код. Нормальной идеи, как дописать в последовательность промежуточные звенья, пока так и не выпестовал.

Загадочный математический гений и писатель продвигают решение задачи о перестановке

Похоже, что скорость генерации перестановок быстрее. Алгоритм генерации я сделал, но последовательность пока не собрал.
Но можно уже протестировать:
Код
Похоже, и правда быстрее. Если еще оптимизировать. Но там substr и strrev но они довольно быстры в php.

Загадочный математический гений и писатель продвигают решение задачи о перестановке

Вроде бы я понял. Два дня промучился, а всего лишь надо было
посмотреть на картинку.

Тогда на мой взгляд алгоритм такой (если не напутал):
1) Крутим до n, например n = 3
123
231
312
2) Проверяем делится ли номер итерации нацело на n (вроде также как в написанном коде у MaxVetrov и Эгана)
Делится, тогда идем по хвосту слева направо (два прохода, чтобы снова не делилось нацело )
3) То, что осталось — идет в начало, перевернутый хвост идет в конец.
4) Снова крутим.
213
132
321
5) Дошли до факториала. Остановка.

Проверил на n=4, n=5 — все верно.
Тогда, чутье подсказывает, что можно без struct, но пока не на сто процентов уверен.

Загадочный математический гений и писатель продвигают решение задачи о перестановке

Ваша последовательность 873 такая же, как по алгоритму MaxVetrov.

Загадочный математический гений и писатель продвигают решение задачи о перестановке

Картинка на всякий случай