Комбинаторная система счисления степени k

Введение

В математике, и в частности в комбинаторике, комбинаторная система счисления степени k (для некоторого положительного целого числа k), также называемая комбинадикой или представлением Маколея целого числа, является соответствием между натуральными числами (включая 0) N и k-комбинациями. Комбинации представляются строго убывающими последовательностями c_k > c_k-1 > … > c₂ > c₁ ≥ 0, где каждый c_i соответствует индексу выбранного элемента в заданной k-комбинации. Различные числа соответствуют различным k-комбинациям и упорядочивают их в лексикографическом порядке. Числа меньше N соответствуют всем k-комбинациям множества {0, 1, …, n − 1}. Соответствие не зависит от размера n множества, из которого берутся k-комбинации, поэтому его можно интерпретировать как отображение из N в k-комбинации, выбранные из N; в этом смысле соответствие является биекцией. Число N, соответствующее (c_k, …, c₂, c₁), определяется следующим образом:

Тот факт, что уникальная последовательность соответствует любому неотрицательному числу N, был впервые отмечен Д. Х. Лемером. Действительно, жадный алгоритм находит k-комбинацию, соответствующую N: выбирают c_k максимально возможным при условии c_k < n, затем c_k-1 максимально возможным при условии c_k-1 < c_k, и так далее. Нахождение числа N по формуле выше из k-комбинации (c_k, …, c₂, c₁) также известно как «ранжирование», а обратная операция (выполняемая жадным алгоритмом) — как «деранжирование»; эти операции известны под этими названиями в большинстве систем компьютерной алгебры и в вычислительной математике. Изначально использовавшийся термин «комбинаторное представление целых чисел» был сокращен Кнутом до «комбинаторной системы счисления», который также приводит более раннюю ссылку; термин «комбинадик» был введен Джеймсом Маккаффри (без ссылки на предыдущую терминологию или работы). В отличие от факториальной системы счисления, комбинаторная система счисления степени k не является системой со смешанным основанием: часть числа N, представленная «цифрой» c_i, не получается из нее простым умножением на разряд. Основное применение комбинаторной системы счисления заключается в том, что она позволяет быстро вычислять k-комбинацию, находящуюся на заданной позиции в лексикографическом порядке, без необходимости явно перечислять все k-комбинации, предшествующие ей; это позволяет, например, случайно генерировать k-комбинации заданного множества. Перечисление k-комбинаций имеет множество применений, включая тестирование программного обеспечения, выборку, контроль качества и анализ лотерейных игр.

Комбинации заказов

Комбинация k множества S является подмножеством S, содержащим k (различных) элементов. Основная цель комбинаторной системы счисления — обеспечить представление каждой из всех возможных k-комбинаций множества S из n элементов одним числом. Выбирая для любого n множество {0, 1, ..., n − 1}, можно организовать представление заданной k-комбинации C таким образом, чтобы оно не зависело от значения n (хотя n, конечно, должно быть достаточно большим); другими словами, рассматривая C как подмножество большего множества при увеличении n, число, представляющее C, не изменится. Таким образом, для комбинаторной системы счисления можно просто рассматривать C как k-комбинацию множества N всех натуральных чисел, не указывая явно n. Чтобы гарантировать, что числа, представляющие k-комбинации множества {0, 1, ..., n − 1}, меньше чисел, представляющих k-комбинации, не содержащиеся в этом множестве, k-комбинации должны быть упорядочены таким образом, чтобы их наибольшие элементы сравнивались первыми. Наиболее естественным упорядочением, обладающим этим свойством, является лексикографическое упорядочение убывающей последовательности их элементов. Так, сравнивая две 5-комбинации C = {0, 3, 4, 6, 9} и C′ = {0, 1, 3, 7, 9}, можно заключить, что C предшествует C′, поскольку они имеют одинаковый наибольший элемент 9, но следующий по величине элемент 6 в C меньше следующего по величине элемента 7 в C′; последовательности, сравниваемые лексикографически, — (9, 6, 4, 3, 0) и (9, 7, 3, 1, 0). Другой способ описать это упорядочение — рассматривать комбинации как описание k установленных битов в двоичном представлении числа, так что C = {c1, ..., ck} описывает число (это связывает различные числа со всеми конечными множествами натуральных чисел); тогда сравнение k-комбинаций можно выполнить, сравнив соответствующие двоичные числа. В примере C и C′ соответствуют числам 1001011001₂ = 60110 и 1010001011₂ = 65110, что снова показывает, что C предшествует C′. Однако это число не является тем, которое нужно использовать для представления k-комбинации, поскольку многие двоичные числа имеют количество установленных битов, отличное от k; необходимо найти относительную позицию C в упорядоченном списке (только) k-комбинаций.

Место комбинации в заказах

Число, связанное в комбинаторной системе счисления степени k с k-комбинацией C, – это число k-комбинаций, строго меньших C в заданном порядке. Это число можно вычислить из C = {ck, …, c2, c1} при условии ck > … > c2 > c1 следующим образом. Из определения порядка следует, что для каждой k-комбинации S, строго меньшей C, существует единственный индекс i, такой что ci отсутствует в S, а ck, …, ci+1 присутствуют в S, и нет другого значения, большего чем ci. Следовательно, можно сгруппировать эти k-комбинации S по возможным значениям i от 1 до k и подсчитать каждую группу отдельно. Для заданного значения i необходимо включить ck, …, ci+1 в S, а оставшиеся i элементов S должны быть выбраны из ci неотрицательных целых чисел, строго меньших ci; при этом любой такой выбор приведет к k-комбинации S, строго меньшей C. Количество возможных выборов равно , что, следовательно, является числом комбинаций в группе i; общее число k-комбинаций, строго меньших C, равно

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

Найти k-комбинацию для данного числа

Данная формула позволяет сразу определить место комбинации из k элементов в лексикографическом порядке. Обратный процесс – нахождение комбинации из k элементов, занимающей заданное место N – требует несколько больше усилий, но также является достаточно простым. По определению лексикографического порядка, две комбинации из k элементов, различающиеся своим наибольшим элементом ck, упорядочиваются путем сравнения этих наибольших элементов. Отсюда следует, что все комбинации с фиксированным значением наибольшего элемента расположены последовательно в списке. Более того, наименьшая комбинация с наибольшим элементом ck имеет ci = i − 1 для всех i < k (для этой комбинации все слагаемые в выражении, кроме ck, равны нулю). Следовательно, ck – это наибольшее число, такое что если k > 1, то остальные элементы комбинации из k элементов образуют комбинацию из k − 1 элементов, соответствующую числу в комбинаторной системе счисления степени k − 1, и, таким образом, могут быть найдены, продолжая тем же способом для N и k − 1 вместо N и k.

Пример

Предположим, кто-то хочет определить 5-ю комбинацию в позиции 72. Последовательные значения для n = 4, 5, 6, … равны 0, 1, 6, 21, 56, 126, 252, …, из которых наибольшее, не превышающее 72, равно 56 при n = 8. Следовательно, c5 = 8, а оставшиеся элементы образуют 4-ю комбинацию в позиции. Последовательные значения для n = 3, 4, 5, … равны 0, 1, 5, 15, 35, …, из которых наибольшее, не превышающее 16, равно 15 при n = 6, следовательно, c4 = 6. Продолжая аналогичным образом поиск 3-й комбинации в позиции, находим c3 = 3, что использует последнюю единицу; это определяет , а оставшиеся значения ci будут максимальными при , а именно . Таким образом, мы нашли 5-ю комбинацию {8, 6, 3, 1, 0}.