Недавно я написал оптимальный решатель для кубика Рубика, который может решить любой скремблированный куб за 20 или меньше ходов. Зацени, если тебе интересно. В любом случае, решение головоломки программным способом включает в себя создание баз данных шаблонов, которые содержат сотни миллионов значений, а именно количество поворотов, необходимых для решения подмножеств куба, например, количество поворотов, необходимых для решения восьми углов. Поскольку такие большие наборы данных могут легко истощить системные ресурсы, значения в базах данных сохраняются последовательно в простых массивах. Индексирование в эти базы данных означает вычисление последовательных индексов для перестановок, по сути, создание минимального идеального хэша для набора частей головоломки.
В этой статье я рассмотрю некоторые алгоритмы вычисления последовательных индексов для перестановок, которые также известны как лексикографический ранг для математиков. Вкратце, алгоритм принимает перестановку набора вещей и преобразует ее в целое число. Я начну с простого алгоритма квадратичной сложности, а затем представлю эквивалентную линейную версию. Наконец, я коснусь индексации частичных перестановок.
Эта штука предназначена для программистов. Существует множество ресурсов, в которых подробно описывается математика, лежащая в основе перестановок ранжирования, но в этой статье основное внимание уделяется реализации и оптимизации кода. Примеры написаны на C ++ и будут скомпилированы с g ++ с использованием стандарта 2017 года. Я также собираюсь несколько раз сослаться на кубик Рубика, так как это отличная иллюстрация групп перестановок; вы должны знать, что такое кубик Рубика и как он движется.
Краткое напоминание о перестановках
Перестановка - это набор чисел или объектов. В отличие от комбинации важен порядок перестановки, поэтому (0 1 2)
отличается от (2 1 0)
. Есть два типа перестановок.
- Перестановки с заменой. Например, ПИН-код дебетовой карты может содержать повторяющиеся цифры.
- Перестановки без замены, как группа людей в очереди. Линия имеет внутренний порядок, и никто не может стоять в очереди дважды.
Индексирование перестановок с заменой тривиально, поэтому я остановлюсь только на последних. С этого момента «перестановка» относится к перестановке без замены.
Для набора из n элементов существует n! возможных перестановок этого набора. Так, например, набор {0 1 2}
можно переставить 3! = 3 * 2 * 1 = 6 способов. Эти 6 перестановок и их лексикографические ранги - вот что нам нужно - это: 0: (0 1 2)
; 1: (0 2 1)
; 2: (1 0 2)
; 3: (1 2 0)
; 4: (2 0 1)
; 5: (2 1 0)
.
Для набора из n элементов, выбранных k способами, существует nPk (читай «n выбрать k») возможных перестановок. Вычисляется как n! / (N-k)!. Например, для набора из 4 предметов можно выбрать 2 из них 4! / (4–2)! = 24/2 = 12 способов: (0 1)
; (0 2)
; (0 3)
; (1 0)
; (1 2)
; (1 3)
; (2 0)
; (2 1)
; (2 3)
; (3 0)
; (3 1)
; (3 2)
. Они ранжируются от 0 до 11 соответственно.
Код Лемера
Вычисление последовательных индексов для перестановок выполняется путем вычисления кода Лемера перестановки и последующего преобразования этого кода Лемера в число с основанием 10. Прежде чем углубиться в этот процесс, давайте на минутку рассмотрим число с основанием 10, например 3120. Число можно разбить на составные части: 3 * 10³ + 1 * 10² + 2 * 10¹ + 0 * 10⁰ = 3120. Как и это число с основанием 10, код Лемера - это просто последовательность цифр; однако у каждой цифры разное основание. Технически это система счисления со смешанным основанием, известная как факторная система счисления. Те же самые цифры, 3, 1, 2, 0, имеют соответствующие основания 3 !, 2 !, 1 !, и 0! в факторной системе счисления. Имея это в виду, преобразовать код Лемера 3120 в основание 10 просто: 3 * 3! +1 * 2! + 2 * 1! + 0 * 0!.
Вычисление индекса перестановки за время O (n²)
В Википедии есть простой квадратичный алгоритм для вычисления кода Лемера перестановки, но он довольно неэффективен для компьютера, поскольку включает в себя объединение элементов из массива. Ниже приводится эквивалентный алгоритм, который легко вычислить. Для каждого элемента перестановки ассоциированная цифра кода Лемера этой перестановки - это тот элемент, который меньше числа элементов перестановки слева от него, которые меньше него (Корф и др.). Я знаю, что это немного грубо для усвоения, поэтому давайте рассмотрим пошаговый пример и вычислим код Лемера для перестановки (2 0 1)
.
- Первый элемент перестановки - 2. Слева от него нет элементов, поэтому первая цифра кода Лемера - 2.
- Второй элемент равен 0. Ни один из элементов слева от него не меньше его, поэтому вторая цифра кода Лемера равна 0.
- И последний элемент равен 1. Он имеет один элемент слева, который меньше его, поэтому последняя цифра кода Лемера (1–1) 0.
Таким образом, (2 0 1)
имеет код Лемера 200. Преобразование его в основание 10 (2 * 2! + 0 * 1! + 0 * 0!) дает 4. Действительно, (2 0 1)
является четвертым (ноль- индексировано) перестановка множества {0 1 2}
, упорядоченная лексикографически.
Стоит отметить, что этот алгоритм работает при условии, что набор чисел в перестановке отсчитывается от нуля. То есть он будет работать для набора {0 1 2}
, но набор {5 6 7}
необходимо будет преобразовать.
Теперь, когда английский трудно читать, а код - легко, вот как это выглядит на C ++.
Для простоты вышесказанное, очевидно, будет работать только с перестановками трех чисел. Позже мы сделаем код универсальным.
Несколько быстрых оптимизаций
В отношении кодов Лемера следует отметить одну вещь: крайняя правая цифра всегда равна 0. Другими словами, независимо от того, какой элемент является последним в перестановке, всегда будет равное количество элементов слева от него, которые меньше его. Тогда очевидной оптимизацией является жесткое кодирование последнего элемента lehmer
на 0 и повторение от 1 до perm.size()-1
. Это верно только для полных перестановок, но не для частичных перестановок (обсуждаемых ниже).
Еще одна простая оптимизация - избавиться от рекурсивной функции factorial
в пользу предварительно вычисленного массива факториалов. Кроме того, последние два вызова factorial
излишни, потому что 1! = 0! = 1.
Помимо этих незначительных изменений, мало что можно сделать для ускорения работы этого алгоритма. Он квадратичный по сложности, и это просто не годится. Решение такой головоломки, как кубик Рубика, требует вычисления перестановок миллиарды раз, и приведенный выше фрагмент кода может (и в моем случае действительно) полностью доминировать над процессорным временем. Нам нужен лучший алгоритм.
Линейный алгоритм
Если вы знакомы с кубиком Рубика или другими головоломками с перестановками, то имя Ричард Корф может показаться вам знакомым. Еще в 1997 году он опубликовал первое оптимальное решение для куба Рубка (и оно работало на Sun SPARC Ultra!). Оказывается, Корф также опубликовал линейный алгоритм кодирования перестановок (крупномасштабный параллельный поиск в ширину). Описание краткое.
Мы просматриваем перестановку слева направо, создавая битовую строку длины n, указывающую, какие элементы перестановки мы видели до сих пор. Изначально в строке все нули. Когда встречается каждый элемент перестановки, мы используем
его как индекс в битовой строке и устанавливаем соответствующий бит в единицу. Когда мы встречаем элемент k в перестановке, чтобы определить количество элементов меньше k слева от него, нам нужно знать количество единиц в первых k битах нашей битовой строки. Мы извлекаем первые k бит, сдвигая строку вправо на n - k. Это сводит проблему к следующему: учитывая битовую строку, подсчитайте количество единиц в ней.
Мы решаем эту проблему за постоянное время, используя битовую строку в качестве индекса в предварительно вычисленной таблице, содержащей количество единиц в двоичном представлении каждого индекса.
Давайте рассмотрим этот алгоритм в качестве примера, снова используя перестановку (2 0 1)
.
- Начните с набора битов длиной 3, инициализированного нулем (
000b
). - Первый элемент перестановки равен 2, поэтому измените бит 2 битового набора:
001b
. Как упоминалось выше, первая цифра кода Лемера всегда совпадает с первой цифрой перестановки, в данном случае 2. - Второй элемент перестановки равен 0, поэтому установите бит 0 набора бит:
101b
. Сдвиньте вправо битовый набор на n - k, где n равно 3, количество элементов в перестановке, а k равно 0, второй элемент перестановки.101b >> (3-0) = 000b
. Подсчитайте количество единиц в результате (countOnes(000b) = 0
) и вычтите его из элемента, чтобы получить цифру Лемера: 0 - 0 = 0. - Третий элемент перестановки равен 1, поэтому установите бит 1 набора бит:
111b
. Сдвиг вправо:111b >> (3-1) = 001b
. Вычтите количество единиц в результате из элемента, чтобы получить цифру Лемера:1 - countOnes(001b) = 1-1 = 0
.
Как и ожидалось, код Лемера - 200.
Выше гипотетическая функция countOnes
просто подсчитывала количество единиц в двоичном представлении числа, поэтому вызов функции с 1, 2, 3, 4 и 5 вернет 1, 1, 2, 1, 2 соответственно. Корф предлагает реализовать это в постоянное время с использованием предварительно вычисленной таблицы.
Вот как алгоритм может выглядеть на C ++. Обратите внимание, что класс std::bitset
индексирует биты справа налево, поэтому самый правый бит имеет индекс 0.
Опять же, код будет работать только для перестановок трех элементов, но общая версия функции приведена в конце статьи.
Индексирование частичных перестановок
Создание индекса для частичной перестановки почти такое же: вычислить код Лемера для перестановки, а затем преобразовать его в число с основанием 10. Но последняя часть - преобразование в base-10 - немного отличается. Для полной перестановки каждая цифра в коде Лемера имеет основание (n-1-i)!, где n - количество цифр в коде Лемера, а i - индекс цифры. Для частичной перестановки основание каждой цифры равно (n-1-i) P (k-1-i), где k - количество элементов, выбранных из набор из n элементов.
Допустим, у нас есть набор из 4 предметов, выбранных двумя способами. (Произвольная) частичная перестановка (1 3)
имеет код Лемера 12. Преобразование этого в основание 10:
1 * (4-1-0)P(2-1-0) + 2 * (4-1-1)P(2-1-1) = 1 * 3P1 + 2 * 2P0 = 5.
Общий метод индексации перестановок
Собирая все вместе, мы получаем общий PermutationIndexer
класс, который может вычислять последовательные индексы как частичных, так и полных перестановок. Пример использования показан внизу в методе main
.
Общая версия в основном такая же, но немного обновлена, чтобы учесть частичные изменения. Напишите мне комментарий, если у вас есть вопросы.
Нужен разработчик?
"Связаться!" Мы небольшая софтверная компания в Фолсоме, штат Калифорния, и будем рады вам помочь.
Ссылки
- Ботто, Бен. Кубик-рубикс-взломщик.
- Корф, Ричард и др. al. Масштабный параллельный поиск в ширину
- Википедия. Факторная система счисления.