Факторная система счисления

Системы счисления
Индусско-арабская система счисления
Западный арабский Восточно-арабский Бенгальский Деванагари Гуджарати Гурмукхи Одиа Сингальский Тамильский Малаялам телугу Каннада Дзонгка тибетский Балийский Бирманский Яванский Кхмерский Лаосский Монгольский Тайский
Восточная Азия
Китайский Сучжоу Хоккиен Японский Корейский вьетнамский Тангутский Счетные стержни
Американец
Кактовик (инупиак)
По алфавиту
Абджад Армянский Ryabhaa Кириллица Geʽez Грузинский Греческий иврит Римский
Бывший
Эгейское море Чердак Вавилонский Брахми Чувашский Цистерцианский Египтянин Этрусский Глаголица Харости майя Муиска Pentimal Доисторический счет Счетные отметки Quipu
Позиционные системы по основанию
2 3 4 5 6 8 10 12 16 20 60
Нестандартные позиционные системы счисления
Биективная нумерация ( 1 ) Знаковое представление ( сбалансированное троичное ) смешанный ( факториал ) отрицательный Комплексно-базовая система ( 2 i ) Нецелое основание счисления ( φ ) Асимметричные системы счисления
Список систем счисления
v т е

В комбинаторике , то факториала система счисления , которая также называется factoradic , является смешанным Radix система позици адаптирована к нумерации перестановок . Он также называется факторной базой , хотя факториалы не функционируют в качестве основы , но и как место значения цифр. Преобразуя число меньше n ! к факториальному представлению, можно получить последовательность из n цифр, которая может быть преобразована в перестановку n простым способом, либо используя их как код Лемера, либо какинверсионное табличное ^[1] представление; в первом случае результирующая карта от целых чисел к перестановкам n перечисляет их в лексикографическом порядке . Общие смешанные системы счисления были изучены Георгом Кантором . ^[2] Термин «факториала номер системы» используется Кнут , ^[3] в то время как французский эквивалент «нумерацией factorielle» впервые был использован в 1888. ^[4] Термин «factoradic», который представляет собой портманто факторного и смешанной системы счисления , похоже, датируется более поздним сроком. ^[5]

Определение [ править ]

Факториальная система счисления представляет собой смешанную систему счисления с основанием системы счисления : i -я цифра справа имеет основание i , что означает, что цифра должна быть строго меньше i , и что (с учетом оснований младших цифр) ее значение, которое нужно умножить на $(i - 1)$ ! (его разрядная стоимость).

Radix	8	7	6	5	4	3	2	1
Место значение	7!	6!	5!	4!	3!	2!	1!	0!
Поместите значение в десятичную дробь	5040	720	120	24	6	2	1	1
Максимально допустимая цифра	7	6	5	4	3	2	1	0

Из этого следует, что крайняя правая цифра всегда равна 0, вторая может быть 0 или 1, третья - 0, 1 или 2 и так далее (последовательность A124252 в OEIS ). Факториальная система счисления иногда определяется как 0! место пропущено, потому что оно всегда равно нулю (последовательность A007623 в OEIS ).

В этой статье представление факториального числа будет помечено нижним индексом "!", Например, 3: 4: 1: 0: 1: 0 _!обозначает 3 ₅ 4 ₄ 1 ₃ 0 ₂ 1 ₁ 0 ₀ , значение которого

= 3 × 5! + 4 × 4! + 1 × 3! + 0 × 2! + 1 × 1! + 0 × 0!

= ((((3 × 5 + 4) × 4 + 1) × 3 + 0) × 2 + 1) × 1 + 0

= 463 ₁₀ .

(Разрядная величина на единицу меньше, чем позиция системы счисления, поэтому эти уравнения начинаются с 5 !.)

Общие свойства смешанных систем счисления счисления также применимы к факторной системе счисления. Например, можно преобразовать число в факториальное представление, производя цифры справа налево, путем многократного деления числа на основание системы счисления (1, 2, 3, ...), принимая остаток как цифры и продолжая с целочисленного частного. , пока это частное не станет 0.

Например, 463 ₁₀ можно преобразовать в факторное представление следующими последовательными делениями:

463 ÷ 1 = 463, остаток 0

463 ÷ 2 = 231, остаток 1

231 ÷ 3 = 77, остаток 0

77 ÷ 4 = 19, остаток 1

19 ÷ 5 = 3, остаток 4

3 ÷ 6 = 0, остаток 3

Процесс завершается, когда частное достигает нуля. Чтение остатков назад дает 3: 4: 1: 0: 1: 0 _!.

В принципе, эта система может быть расширена для представления дробных чисел, хотя вместо естественного расширения разрядов (−1) !, (−2) !, и т.д., которые не определены, симметричный выбор значений системы счисления n = 0 , 1, 2, 3, 4 и т. Д. После точки могут использоваться вместо этого. Опять же, места 0 и 1 могут быть опущены, поскольку они всегда равны нулю. Следовательно, соответствующие значения разряда - 1/1, 1/1, 1/2, 1/6, 1/24, ..., 1 / n !, и т. Д.

Примеры [ править ]

В следующей сортируемой таблице показаны 24 перестановки четырех элементов с разными векторами, связанными с инверсией . Подсчеты левой и правая инверсии и (последний часто называют код Лехмера ), особенно правом быть истолкована как факторные числа. дает позицию перестановки в обратном колексикографическом порядке (порядок по умолчанию в этой таблице), а последняя - позицию в лексикографическом порядке (оба отсчитываются от 0). ${\ displaystyle l}$ ${\ displaystyle r}$ ${\ displaystyle l}$

При сортировке по столбцу, в котором справа пропущен 0, факториальные числа в этом столбце соответствуют номерам индексов в неподвижном столбце слева. Маленькие столбцы являются отражением соседних столбцов, и их можно использовать для приведения их в колексикографический порядок. В крайнем правом столбце показаны суммы цифр факториалов ( OEIS : A034968 в порядке по умолчанию в таблицах).

Факториальные числа заданной длины образуют пермутоэдр, когда они упорядочены поразрядным отношением. Это правильные подсчеты инверсии (также известные как коды Лемера) перестановок четырех элементов.

{\ displaystyle \ leq}


0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 год
22
23

	${\ displaystyle \ pi}$		${\ displaystyle v}$			${\ displaystyle l}$	${\ displaystyle r}$		#
0	1234	4321	000 0	0 000	000 0	0 000	000 0	0 000	0
1	2134	4312	100 0	0 001	001 0	0 100	100 0	0 001	1
2	1324	4231	010 0	0 010	010 0	0 010	010 0	0 010	1
3	3124	4213	110 0	0 011	011 0	0 110	200 0	0 002	2
4	2314	4132	200 0	0 002	020 0	0 020	110 0	0 011	2
5	3214	4123	210 0	0 012	021 0	0 120	210 0	0 012	3
6	1243	3421	001 0	0 100	100 0	0 001	001 0	0 100	1
7	2143	3412	101 0	0 101	101 0	0 101	101 0	0 101	2
8	1423	3241	011 0	0 110	110 0	0 011	020 0	0 020	2
9	4123	3214	111 0	0 111	111 0	0 111	300 0	0 003	3
10	2413	3142	201 0	0 102	120 0	0 021	120 0	0 021	3
11	4213	3124	211 0	0 112	121 0	0 121	310 0	0 013	4
12	1342	2431	020 0	0 020	200 0	0 002	011 0	0 110	2
13	3142	2413	120 0	0 021	201 0	0 102	201 0	0 102	3
14	1432	2341	021 0	0 120	210 0	0 012	021 0	0 120	3
15	4132	2314	121 0	0 121	211 0	0 112	301 0	0 103	4
16	3412	2143	220 0	0 022	220 0	0 022	220 0	0 022	4
17	4312	2134	221 0	0 122	221 0	0 122	320 0	0 023	5
18	2341	1432	300 0	0 003	300 0	0 003	111 0	0 111	3
19	3241	1423	310 0	0 013	301 0	0 103	211 0	0 112	4
20	2431	1342	301 0	0 103	310 0	0 013	121 0	0 121	4
21 год	4231	1324	311 0	0 113	311 0	0 113	311 0	0 113	5
22	3421	1243	320 0	0 023	320 0	0 023	221 0	0 122	5
23	4321	1234	321 0	0 123	321 0	0 123	321 0	0 123	6

В другом примере, наибольшее число, которое может быть представлено шестью цифрами, будет 543210 _!что равно 719 в десятичной системе :

5 × 5! + 4 × 4! + 3x3! + 2 × 2! + 1 × 1! + 0 × 0 !.

Очевидно , что следующий факториала число представление после того, как 5: 4: 3: 2: 1: 0 _!это 1: 0: 0: 0: 0: 0: 0 _!что обозначает 6! = 720 ₁₀ , разрядная цифра системы счисления 7. Таким образом, первое число и его суммированное выражение, приведенное выше, равно:

6! - 1.

Факториальная система счисления обеспечивает уникальное представление каждого натурального числа с заданным ограничением используемых «цифр». Ни одно число не может быть представлено более чем одним способом, потому что сумма последовательных факториалов, умноженная на их индекс, всегда равна следующему факториалу за вычетом единицы:

{\ displaystyle \ sum _ {i = 0} ^ {n} {i \ cdot i!} = {(n + 1)!} - 1.}

Это можно легко доказать с помощью математической индукции или просто заметив, что : последующие члены компенсируют друг друга, оставляя первый и последний член (см. Серию Телескопирования ) $\forall i,i\cdot i!=(i+1-1)\cdot i!=(i+1)!-i!$

Однако при использовании арабских цифр для записи цифр (без учета нижних индексов, как в приведенных выше примерах) их простая конкатенация становится неоднозначной для чисел, у которых «цифра» больше 9. Самый маленький из таких примеров - это число 10 × 10! = 36 288 000 ₁₀ , что может быть записано как A0000000000 _! = 10: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0 _! а не 100000000000 _! = 1: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0 _! что означает 11! = 39 916 800 ₁₀. Таким образом, используя буквы A – Z для обозначения цифр 10, 11, 12, ..., 35, как в другой системе счисления N, получается наибольшее представимое число 36 × 36! - 1. Для произвольно больших чисел необходимо выбрать основу для представления отдельных цифр, например десятичную, и поставить разделительный знак между ними (например, путем добавления индекса каждой цифры по ее основанию, также заданному в десятичном виде, например 2 ₄ 0 ₃ 1 ₂ 0 ₁ , это число также можно записать как 2: 0: 1: 0 _! ). Фактически, факториальная система счисления сама по себе не является системой счисления в том смысле, что она обеспечивает представление всех натуральных чисел с использованием только конечного алфавита символов, поскольку для этого требуется дополнительный знак разделения.

Перестановки [ править ]

Существует естественное отображение между целыми числами $0, ..., п! - 1$ (или , что эквивалентно число с п цифрами в факторном представлении) и перестановками из п элементов в лексикографическом порядке, когда целые числа выражены в factoradic формы. Это отображение получило название кода Лемера (или таблицы инверсии). Например, при $n = 3$ такое отображение будет

десятичный	факторский	перестановка
0 ₁₀	0: 0: 0 _!	(0,1,2)
1 ₁₀	0: 1: 0 _!	(0,2,1)
2 ₁₀	1: 0: 0 _!	(1,0,2)
3 ₁₀	1: 1: 0 _!	(1,2,0)
4 ₁₀	2: 0: 0 _!	(2,0,1)
5 ₁₀	2: 1: 0 _!	(2,1,0)

В каждом случае вычисление перестановки происходит с использованием крайней левой факторадической цифры (здесь 0, 1 или 2) в качестве первой цифры перестановки, а затем удаления ее из списка вариантов (0, 1 и 2). Думайте об этом новом списке вариантов как об индексированном нулем и используйте каждую последующую фактическую цифру для выбора из оставшихся элементов. Если вторая фактическая цифра равна «0», то первый элемент списка выбирается для второй цифры перестановки и затем удаляется из списка. Точно так же, если вторая фактурная цифра равна «1», вторая выбирается и затем удаляется. Последняя фактическая цифра всегда равна "0", и поскольку список теперь содержит только один элемент, он выбирается как последняя цифра перестановки.

Процесс может стать понятнее на более длинном примере. Допустим, нам нужна 2982-я перестановка чисел от 0 до 6. Число 2982 равно 4: 0: 4: 1: 0: 0: 0 _!Фактически радикально, и это число выбирает цифры (4,0,6,2,1,3,5) по очереди, индексируя убывающий упорядоченный набор цифр и выбирая каждую цифру из набора на каждом шагу:

 4: 0: 4: 1: 0: 0: 0 _! ─► (4,0,6,2,1,3,5)factoradic: 4: 0: 4: 1: 0: 0: 0 _! ├─┬─┬─┬─┐ │ ├─┬─┬─┬─┐ ├─┐ │ │ │наборы: (0,1,2,3,4,5,6) ─► (0,1,2,3,5,6) ─► (1,2,3,5,6) ─► (1, 2,3,5) ─► (1,3,5) ─► (3,5) ─► (5) │ │ │ │ │ │ │перестановка: (4, 0, 6, 2, 1, 3, 5)

Естественным индексом для группового прямого произведения двух групп перестановок является конкатенация двух факторадических чисел с двумя нижними индексами "!" S.

 соединенный пара десятичных чисел 0 ₁₀ 0: 0: 0 _!0: 0: 0 _! ((0,1,2), (0,1,2)) 1 ₁₀ 0: 0: 0 _!0: 1: 0 _! ((0,1,2), (0,2,1)) ... 5 ₁₀ 0: 0: 0 _!2: 1: 0 _! ((0,1,2), (2,1,0)) 6 ₁₀ 0: 1: 0 _!0: 0: 0 _! ((0,2,1), (0,1,2)) 7 ₁₀ 0: 1: 0 _!0: 1: 0 _! ((0,2,1), (0,2,1)) ... 22 ₁₀ 1: 1: 0 _!2: 0: 0 _! ((1,2,0), (2,0,1)) ... 34 ₁₀ 2: 1: 0 _!2: 0: 0 _! ((2,1,0), (2,0,1)) 35 ₁₀ 2: 1: 0 _!2: 1: 0 _! ((2,1,0), (2,1,0))

Дробные значения [ править ]

В отличие от систем с одним основанием системы счисления, в которых значения разряда являются основанием ⁿ для положительного и отрицательного целого n, основание факториального числа не может быть расширено до отрицательных значений разряда, поскольку это будет (-1) !, (-2)! и так далее, и эти значения не определены. (см. факториал )

Поэтому одним из возможных расширений является использование 1/0 !, 1/1 !, 1/2 !, 1/3 !, ..., 1 / n! и т. д., возможно, опуская 1/0! и 1/1! места, которые всегда равны нулю.

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

Следовательно, по необходимости факторадическое разложение обратной величины простого числа имеет длину точно такое же простое число (за вычетом единицы, если опущен знак 1/1!). Остальные термины представлены в OEIS как последовательность A046021 . Также можно доказать, что последняя «цифра» или член представления рационального числа с простым знаменателем равна разнице между числителем и простым знаменателем.

Существует также неограничивающий эквивалент для каждого рационального числа, аналогичный тому, что в десятичной дроби 0,24999 ... = 0,25 = 1/4 и 0,999 ... = 1 и т. Д., Который может быть создан путем уменьшения последнего члена на 1, а затем заполнить оставшееся бесконечное количество членов максимально возможным значением системы счисления в этой позиции.

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

$1/2=0.0\ 1_{!}$
$1/3=0.0\ 0\ 2_{!}$
$2/3=0.0\ 1\ 1_{!}$
$1/4=0.0\ 0\ 1\ 2_{!}$
$3/4=0.0\ 1\ 1\ 2_{!}$
$1/5=0.0\ 0\ 1\ 0\ 4_{!}$
$1/6=0.0\ 0\ 1_{!}$
$5/6=0.0\ 1\ 2_{!}$
$1/7=0.0\ 0\ 0\ 3\ 2\ 0\ 6_{!}$
$1/8=0.0\ 0\ 0\ 3_{!}$
$1/9=0.0\ 0\ 0\ 2\ 3\ 2_{!}$
$1/10=0.0\ 0\ 0\ 2\ 2_{!}$
$1/11\ \ =0.0\ 0\ 0\ 2\ 0\ 5\ 3\ 1\ 4\ 0\ A_{!}$
$2/11\ \ =0.0\ 0\ 1\ 0\ 1\ 4\ 6\ 2\ 8\ 1\ 9_{!}$
$9/11\ \ =0.0\ 1\ 1\ 3\ 3\ 1\ 0\ 5\ 0\ 8\ 2_{!}$
$10/11=0.0\ 1\ 2\ 1\ 4\ 0\ 3\ 6\ 4\ 9\ 1_{!}$
$1/12\ \ =0.0\ 0\ 0\ 2_{!}$
$5/12\ \ =0.0\ 0\ 2\ 2_{!}$
$7/12\ \ =0.0\ 1\ 0\ 2_{!}$
$11/12=0.0\ 1\ 2\ 2_{!}$
$1/15=0.0\ 0\ 0\ 1\ 3_{!}$
$1/16=0.0\ 0\ 0\ 1\ 2\ 3_{!}$
$1/18=0.0\ 0\ 0\ 1\ 1\ 4_{!}$
$1/20=0.0\ 0\ 0\ 1\ 1_{!}$
$1/24=0.0\ 0\ 0\ 1_{!}$
$1/30=0.0\ 0\ 0\ 0\ 4_{!}$
$1/36=0.0\ 0\ 0\ 0\ 3\ 2_{!}$
$1/60=0.0\ 0\ 0\ 0\ 2_{!}$
$1/72=0.0\ 0\ 0\ 0\ 1\ 4_{!}$
$1/120=0.0\ 0\ 0\ 0\ 1_{!}$
$1/144=0.0\ 0\ 0\ 0\ 0\ 5_{!}$
$1/240=0.0\ 0\ 0\ 0\ 0\ 3_{!}$
$1/360=0.0\ 0\ 0\ 0\ 0\ 2_{!}$
$1/720=0.0\ 0\ 0\ 0\ 0\ 1_{!}$

Есть также небольшое количество констант, которые имеют шаблонное представление с помощью этого метода:

$e=1\ 0.0\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1..._{!}$
$e^{-1}=0.0\ 0\ 2\ 0\ 4\ 0\ 6\ 0\ 8\ 0\ A\ 0\ C\ 0\ E..._{!}$
$\sin(1)=0.0\ 1\ 2\ 0\ 0\ 5\ 6\ 0\ 0\ 9\ A\ 0\ 0\ D\ E..._{!}$
$\cos(1)=0.0\ 1\ 0\ 0\ 4\ 5\ 0\ 0\ 8\ 9\ 0\ 0\ C\ D\ 0..._{!}$
$\sinh(1)=1.0\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0..._{!}$
$\cosh(1)=1.0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1..._{!}$

См. Также [ править ]

Первоначальная система счисления
Комбинаторная система счисления (также называемая комбинаторной системой )
Алгоритм Штейнхауса – Джонсона – Троттера, алгоритм , который генерирует коды Грея для факторной системы счисления.

Ссылки [ править ]

^ Knuth, DE (1973), «Том 3: Сортировка и поиск», Искусство компьютерного программирования , Addison-Wesley, p. 12, ISBN 0-201-89685-0
↑ Cantor, G. (1869), Zeitschrift für Mathematik und Physik , 14..
^ Knuth, DE (1997), "Том 2: получисловые алгоритмы", Искусство компьютерного программирования (3-е изд.), Addison-Wesley, p. 192, ISBN 0-201-89684-2.
^ Laisant, Charles-Ange (1888), "Sur ли нумерация factorielle, применение AUX перестановок" , Бюллетень де л Société Mathematique де Франс (на французском языке), 16 : 176-183.
^ Термин "factoradic" явно введен в McCaffrey, James (2003), Using Permutations in .NET for Improved Systems Security , Microsoft Developer Network..

Мантачи, Роберто; Rakotondrajao, Fanja (2001), «Представление перестановки, которое знает, что означает« эйлерово » (PDF) , Дискретная математика и теоретическая информатика , 4 : 101–108, заархивировано из оригинала (PDF) 24 мая 2011 г. , проверено 27 марта 2005 г..
Арндт, Йорг (2010). Вопросы вычислительные: идеи, алгоритмы, исходный код . С. 232–238.

Внешние ссылки [ править ]

Калькулятор кода Лемера. Обратите внимание, что их цифры перестановки начинаются с 1, поэтому мысленно сокращает все цифры перестановок на единицу, чтобы получить результаты, эквивалентные тем, что на этой странице.
Факторная система счисления

[1] Knuth, DE (1973), «Том 3: Сортировка и поиск», Искусство компьютерного программирования , Addison-Wesley, p. 12, ISBN 0-201-89685-0

[2] Cantor, G. (1869), Zeitschrift für Mathematik und Physik , 14..

[3] Knuth, DE (1997), "Том 2: получисловые алгоритмы", Искусство компьютерного программирования (3-е изд.), Addison-Wesley, p. 192, ISBN 0-201-89684-2.

[4] Laisant, Charles-Ange (1888), "Sur ли нумерация factorielle, применение AUX перестановок" , Бюллетень де л Société Mathematique де Франс (на французском языке), 16 : 176-183.

[5] Термин "factoradic" явно введен в McCaffrey, James (2003), Using Permutations in .NET for Improved Systems Security , Microsoft Developer Network..