Для предстоящей программки, где можно запускать обратимые клеточные автоматы я хочу сделать возможность задавать любые правила. Как я описывал в посте про Critters, любая перестановка массива от 0 до N является корректным правилом. Значит должна быть возможность задавать перестановку в виде чего-то, что можно скопипастить и вставить в программу.

На одном сайте с обратимыми автоматами перестановка задаётся так:

0,2,8,3,1,5,6,7,4,9,10,11,12,13,14,15

По мне это довольно скучно и не очень удобно.

Поэтому я придумал, что это надо отображать одним числом, которое можно менять на +1, -1, и оно будет корректным. А затем вообще переводить это число в систему счисления с основанием 64, чтобы оно было ещё короче.

Итак, для массива из N различных элементов существует N! возможных вариантов перестановки. Значит можно как-то пронумеровать каждую перестановку одним числом. И если сделать так, то пользователь сможет играться, меняя числа, у него всегда будет получаться корректное правило. Если он, конечно, не задаст число больше N!, но не допустить такую ошибку довольно легко.

Итак, перестановка, показанная вначале может быть записана числом как:

125023449600

Или если же это число перевести в 64-ричную систему счисления:

08D+rQ1

Я сделал маленькую библиотечку чтобы вычислять все эти вещи: permutation_string.

Всеми этими тремя способами в моей программе можно будет задавать правила.

Так же я хочу сделать GUI, чтобы правила можно было перетаскивать мышкой, и чтобы рядом писались все эти данные. Благо на megaui в macroquad сделать это довольно легко. Не знал кстати что Immediate Mode GUI такой простой о_О. Какой-то диссонанс происходит после того как ты делал гуй на всех этих коллбэках. Попробуйте почитать код, и потыкаться.

А теперь я расскажу как именно можно превратить перестановку в одно число.

Пусть у нас есть перестановка А из пяти элементов: [4,1,2,3,0]. Главное свойство любой перестановки - в ней все числа уникальны. Значит можно преобразовать этот массив в немного другой.

Пусть у нас ещё есть такой массив Б: [0,1,2,3,4].

Далее берём нашу перестановку, и говорим по какому индексу находится первый её элемент? 4 находится по индексу 4, так и записываем в массив Ц. Удаляем из массива Б и массива А число 4.

А = [1,2,3,0]. Б = [0,1,2,3]. Ц = [4].

Берём следующее число из А: 1. По какому индексу находится? 1. Так и записываем, удаляем из Б и А эти элементы.

А = [2,3,0]. Б = [0,2,3]. Ц = [4,1].

И теперь начинается самое интересное. Берём следующее число из А: 2. Оно находится по индексу 1. Так и записываем, и удаляем из А и Б.

А = [3,0]. Б = [0,3]. Ц = [4,1,1].

Ну и таким образом у нас в итоге получится: А = []. Б = []. Ц = [4,1,1,1,0].

Что интересного в массиве Ц? У него в каждом следующем элементе максимальное возможное число уменьшается на 1. То есть максимальный Ц = [4,3,2,1,0] возможен для перестановки: [4,3,2,1,0]. А Ц = [0,0,0,0,0] получается для перестановки [0,1,2,3,4].

Получается в Ц у нас хранятся цифры с необычной системой счисления, разной для каждого разряда. Ну и далее можно использовать Ц чтобы получить номер перестановки:

0*0! + 1*1! + 1*2! + 1*3! + 4*4! = 105.

Получается это число находится в промежутке от 0 до N!-1. Вот так мы и пронумеровали каждую перестановку.

Кстати несложно модифицировать алгоритм, чтобы обрабатывать перестановки с повторяющимися элементами.

Говорят что я переизобрёл факториальную Систему Счисления.