Как найти все перестановочные подстановки

Как найти все перестановочные подстановки

Непонятно, почему в качестве A указана не одна подстановка, а две. Даже если это два варианта, то там ответы одинаковые, так как цикл (2143) обратен циклу (1234) в группе. Равенство AB=BA равносильно BA^{-1}=A^{-1}B после домножения слева и справа на A^{-1}. Поэтому перестановочность с A равносильна перестановочностью с A^{-1}.

Итак, считаем далее, что A=(1234). Начнём с того, что любые степени одного и того же элемента перестановочны. Поэтому мы уже знаем 4 элемента, которые перестановочны с A. Это E=A^0, A=A^1, A^2=(13)(24), A^3=(1432).

Докажем, что в данном случае никаких других перестановочных с A элементов нет. Равенство AB=BA равносильно тому, что B^{-1}AB=A. Левая часть имеет название сопряжённого элемента (говорят, что мы A сопрягаем при помощи B).

Будем использовать такой несложный, но важный факт. Запишем B не в виде циклов, а как “двухэтажное” выражение: сверху 1 2 3 4, снизу a, b, c, d (перестановка). Легко проверить, что B^{-1}AB=(abcd), то есть в циклах элементы меняются на свои образы относительно B. Это простое в применении правило нахождения сопряжённого элемента. Проверяется оно элементарно: символ a при B^{-1} переходит в 1. Потом 1 в 2 при A. Потом 2 в b при B. Значит, при последовательном выполнении B^{-1}AB слева направо, a переходит в b. Аналогично, b переходит в C, и так далее.

Теперь у нас из B^{-1}AB=A возникло равенство (abcd)=(1234). Это не значит, что a=1, b=2, c=3, d=4, потому что цикл (1234) можно записать ещё тремя способами: (2341), (3412), (4123). Итого 4 варианта. Каждый из них даёт некоторое значение B. Значит, перестановочных с A подстановок не больше четырёх, а 4 у нас уже имеются. Значит, мы всё нашли.

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

Источник

Мы получили два эквивалентных определения определителя третьего порядка (формулы (4) и (5)). С помощью (4) определитель 3-го порядка вводится с помощью определителей второго порядка (разложение по столбцу). При этом легко проверяется, что все столбцы равноправны. Аналогично рекуррентным образом можно определить определитель n-го порядка (определитель квадратной матрицы n-го порядка), т. е.

=

= (7)

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

Пусть дан упорядоченный набор из N элементов. Элементы этого набора занумеруем числами 1, 2, 3, … , n. Очевидно, вместо того, чтобы говорить об элементах, можно говорить об их номерах.

Определение 5. Перестановкой Из N Чисел (или N символов) называется расположение этих чисел (или символов) в любом определённом порядке (без повторений).

Теорема 1. Число перестановок из N Символов равно n!

Доказательство. Составляя перестановку, в качестве первого её элемента можно выбрать точно n символов. Если первый элемент выбран, то в качестве второго элемента можно выбрать любой из оставшихся (n – 1) символов. Следовательно, первые два места можно заполнить n×(n – 1 ) способами. Если два места в перестановке уже заполнены, то на третье место можно поставить любой из оставшихся (n – 2) символов. Следовательно, первые три места можно заполнить n×(n – 1)×(n – 2 ) способами. Продолжая этот процесс, получим, что все n мест в перестановке можно заполнить n×(n – 1)×(n – 2)×…×3×2×1 = n! способами.

Говорят, что числа К и Р образуют в перестановке (…К…р…) Инверсию, если К > Р, Но в перестановке К стоит раньше Р. Перестановка называется Чётной, если она содержит чётное число инверсий. Перестановка называется Нечётной, если она содержит нечётное число инверсий.

Пример. 1) Перестановка (9, 7, 1, 3, 4, 8, 5, 2, 6) чётная. В ней число 9 образует инверсии со всеми стоящими за ней числами, их 8. Число 7 образует новые инверсии со всеми стоящими за ней числами, кроме числа 8, их 6. Число 1 не образует ни одной новой инверсии. Числа 3 и 4 образуют по одной новой инверсии с числом 2. Число 8 образует ещё инверсии с 5, 2 и 6, их 3. Число 5 образует инверсию с числом 2. Итак, получается 8 + 6 + 1 + 1 + 3 + 1 = 20 инверсий.

2) Перестановка ( 2, 1, 3, 5, 4, 6, 9, 8, 7) нечётная. В ней инверсии образуют пары чисел 2 и 1, 5 и 4, 9 и 8, 9 и 7, 8 и 7. Получилось 5 инверсий.

Если в перестановке два символа поменять местами, а все остальные символы оставить на старых местах, то получим новую перестановку. Это преобразование перестановки называется Транспозицией.

Теорема 2. Всякая транспозиция меняет чётность перестановки.

Доказательство. Пусть в перестановке символы К и Р меняются местами. При этом возможны два случая.

1) Символы К и Р В данной перестановке стоят рядом, т. е. (…К, Р …). После транспозиции получится перестановка (….Р, к …). Если К и Р Составляли инверсию в данной перестановке, то после инверсии они уже не будут составлять инверсию и наоборот. Число инверсий, которые К и Р Составляли в данной перестановке с остальными символами, не изменится. Следовательно, число инверсий изменится на 1, т. е. чётность перестановки изменится.

2) Символы К и Р В данной перестановке стоят не рядом, т. е. (….К,…,р…). После транспозиции получится перестановка (…Р,…,к…). Число инверсий, которые К и Р Составляли в данной перестановке с символами, стоящими перед К И после Р, не изменится. Если между К и Р Стоят M символов, то переставить К и Р можно следующим образом: переставить К последовательно с каждым из этих M Символов, затем переставить К и Р, затем в обратном порядке переставить Р с каждым из этих M символов. Получим 2m + 1 транспозиций соседних символов. По доказанному каждая из них меняет чётность перестановки. Итак, чётность перестановки изменилась.

Следствие. При n > 1 число чётных перестановок равно числе нечётных перестановок и равно 0,5×n!.

Определение 6. Подстановкой из N символов ( или Подстановкой N-ой степени) называется любое взаимнооднозначное отображение множества этих символов на себя.

Элементы данного множества будем обозначать 1, 2, …, n. Подстановка А может быть записана так: если число К переходит в число aК, то А = . Если в записи подстановки А Некоторые столбцы поменять местами, то получится то же самое отображение данного множества, т. е. та же подстановка. Например,

А = = .

Запись подстановки А = будем называть стандартной. Всякую подстановку можно записать в стандартном виде. Верхнюю и нижнюю строки подстановки можно рассматривать как перестановки. Подстановка А называется чётной, если её верхняя и нижняя строки есть перестановки одинаковой чётности, т. е. общее число инверсий в них – чётное. В противном случае А Называется Нечётной. Так как перестановка столбцов равносильна транспозиции как в верхней так и в нижней строке, то при перестановке столбцов чётность подстановки не изменится, поэтому чётность подстановки можно вычислять по её стандартному виду и в этом случае она совпадает с чётностью нижней строки.

Подстановка Е = называется Тождественной Или Единичной.

Произведением двух подстановок одного и того же порядка называется результат последовательного выполнения тех отображений, которые задают эти подстановки. Например, если А = , В = , то

А×В = . Действительно, первая подстановка переводит 1 в 5, вторая переводит 5 в 4, следовательно, окончательно 1 перейдёт в 4. Аналогично, , , следовательно, ; , , следовательно, ; , , следовательно, ; , , следовательно, ; , , следовательно, .

Аналогично получаем, что В×А = . Отсюда следует, что умножение подстановок не подчиняется коммутативному закону. Но можно проверить, что (А×В)×С = А×(В×С) для любых подстановок А, В, С Одного и того же порядка. Очевидно, А×Е = Е×А для любой подстановки А, Если А и Е Одного порядка. Для подстановок А = и В = очевидно А×В = В×А = Е. Следовательно, А-1 = В, т. е. каждая подстановка имеет обратную.

< Предыдущая   Следующая >
Источник

Макеты страниц

Эти понятия играют важную роль в комбинаторике и мы напомним их.

Подстановкой называется биекция конечного множества на себя (рис. 12).

Подстановку часто изображают в виде соответствия между двумя строками:

первую строку называют «операндом», вторую — «результатом».

Рис. 12.

Порядок, в котором записывается операнд, вообще говоря, несуществен:

Подстановку можно представить, выписывая в строку элементов и подписывая под каждым из них его образ при биекции.

Перестановкой множества называется вполне упорядоченное множество, состоящее из всех элементов Если состоит из элементов, то имеется таких множеств. Таким образом, подстановку можно охарактеризовать перестановкой, задаваемой нижней строкой.

Произведение двух подстановок. Структура группы. Пусть — образ элемента при подстановке образ элемента у при подстановке Определим подстановку

(кликните для просмотра скана)

Например, если

то

На рис. 13 изображено это произведение. За единичную подстановку примем

Для каждой подстановки существуют симметричная ей слева и симметричная ей справа, совпадающие между собой (как на рис. 14).

Легко проверить свойство ассоциативности:

Таким образом, выполняются все групповые аксиомы. Множество подстановок элементов образует группу, называемую симметрической группой

Группа не коммутативна, так как для некоторых элементов

Прежде чем ввести понятие цикла, укажем еще одно изображение подстановки, пример которого приведен на рис. 15.

С другой стороны, подстановку можно записать с помощью перестановки, если первые строки всех подстановок взять одинаковыми. Например,

Цикл. Пусть задана биекция подмножества а на себя. Если мы проходим, следуя ей, все элементы начиная с некоторого и возвращаясь в него, то получаемую подстановку назовем циклом. Например, на рис. 16 представлен цикл, (1652734), на рис. 17 представлены циклы (1427) и (365), на рис. 18 — циклы (17), (2), (3), (456). Запишем эти подстановки с помощью циклов:

Обычно цикл записывают, начиная с наименьшего элемента (или с элемента с наименьшим индексов). Например, Часто удобно заменить символы в подстановке

на целые числа (или на элементы с целочисленными индексами)

Цикл, состоящий из элементов, называют -циклом. Например, (1652734) на рис. 16 есть -цикл; (1427) на рис. 17 есть 4-цикл; (2), (17), (456) на рис. 18 являются соответственно 1-циклом, 2-циклом, 3-циклом.

Рис. 17

Рис. 18.

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

Пример. На рис. 16 , на рис. 17 , на рис. 18 .

Будем иногда писать (0, 0, 1, 1) вместо (0, 0, 1, 1, 0, 0, 0), если это не приводит к недоразумению.

Теорема Для любого класса подстановок элементов

Это очевидно, ибо -цикл содержит элементов, а всего элементов в подстановке

Теорема II. Обозначим через число подстановок класса Тогда

где

Рассмотрим -циклов в подстановке из заданного класса. Так как безразлично, какой элемент брать в качестве начального в каждом из этих циклов, то эту подстановку можно записать различными способами.

Рис. 19.

Учитывая, что циклы можно переставлять между собой, получаем различных способов записи. Следовательно, любую подстановку из класса можно записать способами. Так как всего имеется возможных записей подстановок из этого класса, то получаем (16.10).

Пример. Рассмотрим класс (1,0, 1,0) при Тогда

Эти подстановки представлены на рис. 19.

Степени подстановки. Определим последовательно

Очевидно, что все эти подстановки коммутативны:

Например, если

то

Все степени некоторой подстановки можно изобразить в виде схемы, как это показано на рис. 20. Однако если подстановка обладает несколькими циклами, такая схема громоздка.

Рис. 20.

Аналогично вводятся отрицательные степени:

Порядок подстановки. Порядок подстановки есть наименьшее целое положительное число такое, что

Например, как это видно из рис. 20,

а из рис. 21 заключаем, что

Количество элементов в цикле называют порядком цикла. Например, -цикл имеет порядок

Теорема III. Порядок подстановки равен наименьшему общему кратному порядков циклов, определяющих класс эквивалентности, которому она принадлежит.

Пусть подстановка принадлежит классу Ее всегда можно представить в виде произведения подстановок (перестановочных между собой), первая из которых содержит -циклов, вторая содержит -циклов и -циклов, содержит 1-циклов и -циклов. На рис, 22 дан пример такого разложения.

Таким образом,

В силу коммутативности

Для того чтобы была единичной подстановкой, необходимо и достаточно, чтобы

Рис. 21.

Но наименьшее целое число для которого это свойство выполняется, есть наименьшее общее кратное тех чисел для которых

Рис. 22.

Рис. 23.

Транспозиция. Транспозиция есть подстановка из класса

Она переставляет между собой два элемента, не меняя расположения остальных. Пример транспозиции (рис. 23)

Теорема IV. Всякая подстановка разлагается в произведение транспозиций.

Способ доказательства теоремы проиллюстрируем на примере.

Пусть

и заданы транспозиции

Тогда

как видно из рис. 24.

Рис. 24.

Произведение различных транспозиций не коммутативно. Например,

но

Четность перестановки. Рассмотрим перестановку на множестве из элементов. С этим множеством свяжем неупорядоченное множество образованное парами различных элементов причем элементы в каждой паре записываются в том же порядке, что и в . Например, с перестановкой

получающейся из подстановки на рис. 25, связываем неупорядоченное множество

Рис. 26 показывает, как можно легко получить без пропусков и повторений.

С другой перестановкой

получающейся из подстановки на рис. 27, связывается множество, которое легко выписывается с помощью рис. 28.

Часть пар в совпадают, а другие отличаются порядком их элементов. Пусть число таких инверсий. Если четно, то скажем, что имеет ту же четность, что и . Сравнивая (16.34) и (16 32), видим, что имеется восемь инверсий (отмеченных на рис. 28 звездочкой), т. е. четности совпадают.

Рис. 25

Рис. 26

Рис. 27.

Рис. 28.

Отношение имеют одинаковую четность» есть отношение эквивалентности (рефлексивность, симметричность и транзитивность очевидны).

Так как всего имеется перестановок и каждый класс содержит одно и то же число элементов, то это число равно Исходная перестановка рассматривается как четная.

Четность подстановки. Подстановка сопоставляет любой перестановке перестановку . Например, если

то

или символически

По последовательности перестановок и подстановке можно выписать последовательность образов

Четности и либо все одинаковы, либо все противоположны Действительно, определим подстановку

Рассматривая как нижние строки соответствующих подстановок, имеем

Отсюда следует, что число инверсий при переходе от совпадает с числом инверсий при переходе от Таким образом, подстановки также распадаются на два класса (подстановка принадлежит четному классу). Имеется четных подстановок и столько же нечетных.

Группы и подгруппы подстановок. Рассмотрим все подстановки множества из элементов. Как было показано, они образуют группу, элементы которой можно разбить на два класса: четных и нечетных подстановок. Четные подстановки образуют подгруппу:

1) единичная подстановка четна по определению;

2) обратная к четной подстановке также четная;

3) произведение четных подстановок четно.

Сформулируем еще несколько теорем.

Теорема Всякая транспозиция есть нечетная подстановка.

Теорема очевидна в силу определения транспозиции.

Так как произведение транспозиций дает четную подстановку, а произведение транспозиций — нечетную, то справедливо следующее утверждение:

Теорема VI. Если подстановка разложена в произведению транспозиций, то число их четно или нечетно в зависимости от того, четна или нечетна Верно и обратное утверждение.

Теорема VII. Если число четных циклов четно, то подстановка четна, если это число нечетно, то подстановка нечетна.

Приведем несколько примеров.

Подстановки класса (1, 2, 0, 1, 0, 0, 0, 0, 0) нечетны, так как содержат четных циклов Подстановки класса (0, 1, 1, 1, 0, 0, 0, 0, 0) четны, так как содержат четных циклов. Подстановки класса (3,0, 1,0, 0,0) четны, так как не содержат четных циклов.

Теорема VIII (теорема Кэли). Всякая конечная группа изоморфна некоторой группе подстановок ее элементов.

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

1

Оглавление

  • ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
  • ГЛАВА 1. ПЕРЕСЧЕТ. ПРИМЕНЕНИЕ ПРОИЗВОДЯЩИХ ФУНКЦИЙ
  • § 2. Теоретико-множественное произведение. Понятие r-выборки
  • § 3. Размещения. Сочетания
  • § 4. Пересчет. Перечисление. Классификация. Оптимизация
  • § 5. Производящие функции
  • § 6. Сведения о конечноразностных операторах
  • § 7. z-преобразование
  • § 8. Применение производящей функции. Энумераторы и денумераторы сочетаний
  • § 9. Денумераторы размещений
  • § 10. Основные последовательности и формулы для пересчета
  • ГЛАВА II. РАЗВИТИЕ МЕТОДОВ ПЕРЕСЧЕТА
  • § 12. Формула включения и исключения
  • § 13. Использование общего метода решета в теории чисел
  • § 14. Задача о встречах. Беспорядки и совпадения
  • § 15. Перманент матрицы
  • § 16. Группы подстановок. Перестановки. Транспозиции
  • § 17. Денумераторы цикловых классов
  • § 18. Классифицирование. Схема размещения элементов по ячейкам
  • § 19. Урновые схемы
  • § 20. Задача о супружеских парах, или задача Люка
  • § 21. Перестановки с запретными положениями. Размещение по ячейкам
  • § 22. Противоречивые перестановки
  • § 23. Латинские прямоугольники
  • ГЛАВА III. СВОЙСТВА ГРАФОВ
  • § 25. Граф. Определение
  • § 26. Понятие пути
  • § 27. Сильно связный граф. Разложение на максимальные сильно связные подграфы. Транзитивное замыкание и пересчет путей
  • § 28. Порядковая функция графа без контуров
  • § 29. Функция Гранди
  • § 30. Внутренняя устойчивость. Внешняя устойчивость
  • § 31. Ядра графа
  • § 32. Основные понятия для неориентированных графов
  • § 33. Хроматическое число. Хроматический класс
  • § 34. Клика. Максимальная клика
  • § 35. p-цветный граф. Граф с p отображениями. Неориентированный мультиграф, или неориентированный p-граф
  • § 36. Плоские p-графы
  • § 37. Подмножество сочленения
  • § 38. Прадерево. Дерево
  • § 39. Конечные структуры
  • ГЛАВА IV. ПЕРЕЧИСЛЕНИЕ
  • § 41. Метод латинской композиции
  • § 42. Перечисление путей
  • § 43. Перечисление элементарных путей
  • § 44. Перечисление элементарных контуров
  • § 45. Перечисление последовательностей с повторением
  • § 46. Перечисление факторов графа
  • § 47. Перечисление рассечений
  • § 48. Другие методы и задачи перечисления
  • ГЛАВА V. ОПТИМИЗАЦИЯ
  • § 50. Числовая функция на графе
  • § 51. Оптимизация пути в графе без контуров. Теоремы оптимальности
  • § 52. Метод динамического программирования
  • § 53. Последовательные графы
  • § 54. Метод прогрессивных разделений и оценок (метод ветвления и ограничения)
  • § 55. Нахождение хорошего решения эвристическим методом
  • § 56. Применение методов Монте-Карло
  • § 57. Понятие k-оптимальности
  • § 58. Оптимизация на прадереве. Отыскание оптимального дерева, являющегося частичным графом
  • § 59. Задачи о временном упорядочении
  • § 60. Оптимизация потока в сети
  • § 61. Простой граф. Покрытие. Паросочетание
  • § 62. Задача о назначении
  • ПРИЛОЖЕНИЕ А. БИНАРНАЯ БУЛЕВА АЛГЕБРА. КОЛЬЦО КЛАССОВ ВЫЧЕТОВ ПО МОДУЛЮ n. ПОЛЯ ГАЛУА ХАРАКТЕРИСТИКИ p
  • А3. Кольцо классов вычетов по модулю n
  • А4. Поля Галуа
  • А5. Алгебра по модулю 2
  • ПРИЛОЖЕНИЕ Б. КОДИРОВАНИЕ. КОДЫ, ОБНАРУЖИВАЮЩИЕ ОШИБКИ
  • Б3. Коды, обнаруживающие и исправляющие ошибки
  • Б4. Аналогия между циклическими и линейными кодами
  • Б5. Коды сцепления
  • Б6. Декодирование перестановками
  • ЛИТЕРАТУРА
Источник

Содержание

Подстановки

проверено

Подстановка

Транспозиции и циклы

Определение 3. Циклической подстановкой2), или циклом3) называется такая подстановка $piin S_n$, что при повторении ее достаточное число раз всякий из действительно перемещаемых ею символов может быть переведен в любой другой из этих символов. Для обозначения цикла используют запись $(iquadpi(i)quadldotsquadpi^{t-1}(i))$, где $t$ — число действительно перемещаемых символов подстановки, которое называется длиной цикла4).

Пример 3. В подстановке

$pi=begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\ 3 & 2 & 6 & 5 & 1 & 4 & 7 & 8end{pmatrix}$

действительно перемещаемыми символами являются 1, 3, 4, 5, 6. Выберем любой из них, например, 3. $pi(3)=6,,pi(6)=4,,pi(4)=5$, $pi(5)=1,,pi(1)=3$. Поэтому цикл можно записать как $(3quad 6quad 4quad 5quad 1)$.

Определение 4. Циклы называются независимыми5), если они не имеют общих действительно перемещаемых символов.

Предложение 1. Любая подстановка $pineq e$ из $S_n$ может быть разлжена в произведение попарно независимых циклов. Такое представление определено однозначно с точностью до порядка перемножения циклов.

Пример 4. $begin{pmatrix}1 & 2 & 3 & 4 & 5\ 3 & 5 & 1 & 2 & 4end{pmatrix}=(1quad 3)(2quad 5quad 4)$ — разложение подстановки в произведение попарно независимых циклов.

Определение 5. Цикл длины 2 называется транспозицией6).

Предложение 2. Каждая подстановка может быть представлена в виде произведения транспозиций.

В отличие от представления в произведение попарно независимых циклов, представление в виде произведения транспозиций может не быть единственным.

Пример 5. Подстановка $begin{pmatrix}1 & 2 & 3 & 4\ 2 & 3 & 1 & 4end{pmatrix}$ может быть разложена в произведение транспозиций $(1quad 3)(1quad 2)$ или $(1quad 3)(2quad 4)(1quad 2)(1quad 4)$.

Четность подстановки

См. также

Литература

Наверх

Источник

Как перебрать все перестановки и о факториальном разложении натуральных чисел

Время на прочтение
3 мин

Количество просмотров 26K

Задачи о переборе всех возможных перестановок заданного множества сущностей возникают в программировании достаточно часто. Как известно из комбинаторики, число возможных перестановок n предметов равно попросту факториалу числа n

n! = n * (n — 1) * (n – 2) * … * 3 * 2 * 1

Факториал – достаточно быстро растущая функция, об этом говорит ее асимптотика (формула Стирлинга), хотя достаточно посмотреть на факториалы нескольких первых членов натурального ряда:

1! 1
2! 2
3! 6
4! 24
5! 120
6! 720
7! 5 040
8! 40 320
9! 362 880
10! 3 628 800
11! 39 916 800
12! 479 001 600
13! 6 227 020 800
14! 87 178 291 200
15! 1 307 674 368 000

Как видно, факториал 13-ти уже не умещается в тип данных long.

Если задаться целью найти однозначное соответствие между номером перестановки — числом в диапазоне от 1 до n! – и ее реализацией, можно натолкнуться на один очень интересный математический факт.

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

196610 = 1*103 + 9 * 102 + 6 * 101 + 6 (*100)

101100012 = 1 * 27 + 0 * 26 + 1 * 25 + 1 * 24 + 0 * 23 + 0 * 22 + 0 * 21 + 1 * 20 (=17710)

Позиционная запись, помимо компактности, обладает тем бесценным свойством, что алгоритм выполнения арифметических операций оказывается чрезвычайно простым (есть историческая байка, что в школах средневековья изучение арифметики занимало несколько лет, поскольку вычисления над числами в НЕпозиционной римской записи имели множество правил для того, чтобы провести простое сложение!)

Оказывается, существует, и является однозначным разложение и способ записи числа, в котором каждый разряд в таком его представлении умножается на ФАКТОРИАЛ номера позиции.

Покажем это на примерах:

1985 = 2 * 6! + 4 * 5! + 2 * 4! + 2 * 3! + 2 * 2! + 1 * 1!

2 940 861 129 405 = 2*15! + 3*14! + 10*13! + 3*12! + 6*11! + 8*10! + 4*9! + 8*8! + 0*7! + 2*6! + 2*5! + 1*4! + 3*3! + 1*2! + 1*1!

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

Более математически строго: каждое натуральное число n можно единственным образом представить в виде следующей суммы:

где
km <= m – коэффициент при m! — он же разряд числа в его факториальном представлении,
p – количество «разрядов» в числе в его факториальном представлении
то есть число записывается как kp kp-1 kp-2… k2 k1

Теперь опишем, как использовать факториальное представление (разложение) числа для генерации соответствующей перестановки. Расположим n элементов в порядке возрастания индекса от 1 до n. Для каждого числа в диапазоне 0..n!-1 произведем факториальное разложение, вычислив его коэффициенты km. В разложении нуля коэффициенты km будут все нули, в разложении числа n!-1 все km = m, m меняется в диапазоне от 0 до n-1. Теперь поместим элемент с номером m на место с номером km+1, считая лишь свободные места, оставшиеся к этому шагу. Фактически, эта процедура повторяет рассуждения, которые приводятся при вычислении числа возможных перестановок из n элементов – первый элемент может быть размещен n способами, второй – (n-1) способом и так далее. Таким образом, мы получим все возможные перестановки из n несовпадающих элементов.

Проиллюстрируем это для 5 предметов (120 вариантов перестановок) и перестановки №77
77 = 3 * 4! + 0 * 3! + 2 * 2! + 1 * 1!

Не являясь программистом-практиком, я все же выскажу предположения (теоретические)), как можно было бы использовать подобное разложение. Можно разбить общее число возможных перестановок на поддиапазоны по числу имеющихся параллельных потоков исполнения, и извлекать текущую перестановку прямо из представления переменной цикла в факториальной записи. Разложение в факториальную форму – задача достаточно вычислительно сложная, но можно разложить только стартовое число поддиапазона, а затем просто прибавлять единицу, перенося ее в следующий разряд в случае переполнения.

Источник

Добавить комментарий