Недавно я написал оптимальный решатель для кубика Рубика, который может решить любой скремблированный куб за 20 или меньше ходов. Зацени, если тебе интересно. В любом случае, решение головоломки программным способом включает в себя создание баз данных шаблонов, которые содержат сотни миллионов значений, а именно количество поворотов, необходимых для решения подмножеств куба, например, количество поворотов, необходимых для решения восьми углов. Поскольку такие большие наборы данных могут легко истощить системные ресурсы, значения в базах данных сохраняются последовательно в простых массивах. Индексирование в эти базы данных означает вычисление последовательных индексов для перестановок, по сути, создание минимального идеального хэша для набора частей головоломки.

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

Эта штука предназначена для программистов. Существует множество ресурсов, в которых подробно описывается математика, лежащая в основе перестановок ранжирования, но в этой статье основное внимание уделяется реализации и оптимизации кода. Примеры написаны на C ++ и будут скомпилированы с g ++ с использованием стандарта 2017 года. Я также собираюсь несколько раз сослаться на кубик Рубика, так как это отличная иллюстрация групп перестановок; вы должны знать, что такое кубик Рубика и как он движется.

Краткое напоминание о перестановках

Перестановка - это набор чисел или объектов. В отличие от комбинации важен порядок перестановки, поэтому (0 1 2) отличается от (2 1 0). Есть два типа перестановок.

  1. Перестановки с заменой. Например, ПИН-код дебетовой карты может содержать повторяющиеся цифры.
  2. Перестановки без замены, как группа людей в очереди. Линия имеет внутренний порядок, и никто не может стоять в очереди дважды.

Индексирование перестановок с заменой тривиально, поэтому я остановлюсь только на последних. С этого момента «перестановка» относится к перестановке без замены.

Для набора из 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).

  1. Первый элемент перестановки - 2. Слева от него нет элементов, поэтому первая цифра кода Лемера - 2.
  2. Второй элемент равен 0. Ни один из элементов слева от него не меньше его, поэтому вторая цифра кода Лемера равна 0.
  3. И последний элемент равен 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).

  1. Начните с набора битов длиной 3, инициализированного нулем (000b).
  2. Первый элемент перестановки равен 2, поэтому измените бит 2 битового набора: 001b. Как упоминалось выше, первая цифра кода Лемера всегда совпадает с первой цифрой перестановки, в данном случае 2.
  3. Второй элемент перестановки равен 0, поэтому установите бит 0 набора бит: 101b. Сдвиньте вправо битовый набор на n - k, где n равно 3, количество элементов в перестановке, а k равно 0, второй элемент перестановки. 101b >> (3-0) = 000b. Подсчитайте количество единиц в результате (countOnes(000b) = 0) и вычтите его из элемента, чтобы получить цифру Лемера: 0 - 0 = 0.
  4. Третий элемент перестановки равен 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.

Общая версия в основном такая же, но немного обновлена, чтобы учесть частичные изменения. Напишите мне комментарий, если у вас есть вопросы.

Нужен разработчик?

"Связаться!" Мы небольшая софтверная компания в Фолсоме, штат Калифорния, и будем рады вам помочь.

Ссылки