Комбинаторная система счисления - Combinatorial number system

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

Номер N соответствующий (c_k,...,c₂,c₁) дан кем-то

{ displaystyle N = { binom {c_ {k}} {k}} + cdots + { binom {c_ {2}} {2}} + { binom {c_ {1}} {1}}. }

Тот факт, что уникальная последовательность так соответствует любому числу N наблюдался Д. Х. Лемер.^[1] Действительно жадный алгоритм находит k-комбинация, соответствующая N: брать c_k максимальный с ${ Displaystyle { tbinom {c_ {k}} {k}} leq N}$ , а затем взять c_{k − 1} максимальный с ${ Displaystyle { tbinom {c_ {k-1}} {k-1}} leq N - { tbinom {c_ {k}} {k}}}$ , и так далее. Нахождение числа N, используя формулу выше, из k-комбинация (c_k,...,c₂,c₁) также известен как «ранжирование», а противоположная операция (заданная жадным алгоритмом) как «снятие рейтинга»; эти операции известны под этими именами в большинстве системы компьютерной алгебры, И в вычислительная математика.^[2]^[3]

Первоначально используемый термин «комбинаторное представление целых чисел» сокращен до «комбинаторной системы счисления» Knuth,^[4]кто также дает гораздо более старую ссылку;^[5]термин «комбинированный» введен Джеймсом Маккаффри ^[6] (без ссылки на предыдущую терминологию или работу).

в отличие от факториальная система счисления, комбинаторная система счисления степеней k это не смешанный корень система: часть ${ displaystyle { tbinom {c_ {i}} {i}}}$ числа N представлен "цифрой" c_я не получается из него простым умножением на разряд.

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

Комбинации для заказа

А k-комбинация набора S это подмножество S с k (отдельные) элементы. Основная цель комбинаторной системы счисления состоит в том, чтобы обеспечить представление каждого из них одним числом всех ${ displaystyle { tbinom {n} {k}}}$ возможный k-комбинации набора S из п элементы. Выбор, для любого п, {0, 1, ..., п − 1} как такой набор, можно организовать, что представление данного k-комбинация C не зависит от значения п (несмотря на то что п конечно должен быть достаточно большим); другими словами, учитывая C как подмножество большего набора путем увеличения п не изменит число, представляющееC. Таким образом, для комбинаторной системы счисления достаточно рассмотреть C как k-комбинация набора N всех натуральных чисел, без явного упоминания п.

Чтобы гарантировать, что числа, представляющие k-комбинации {0, 1, ..., п − 1} меньше, чем представляющие k-комбинации, не содержащиеся в {0, 1, ..., п − 1}, 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 = {c₁,...,c_k} описывает число

{ displaystyle 2 ^ {c_ {1}} + 2 ^ {c_ {2}} + cdots + 2 ^ {c_ {k}}}

(это связывает различные числа с все конечные наборы натуральных чисел); затем сравнение k-комбинации могут быть выполнены путем сравнения связанных двоичных чисел. В примере C и C'соответствуют номерам 1001011001₂ = 601₁₀ и 1010001011₂ = 651₁₀, что еще раз показывает, что C приходит раньше C'. Это число, однако, не то, которое хотят обозначить k-комбинация с, поскольку многие двоичные числа имеют количество повышенных битов, отличное от k; нужно найти относительное положение C в упорядоченном списке (только) k-комбинации.

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

Число, ассоциированное в комбинаторной системе счисления степени k к k-комбинация C это количество k-комбинации строго меньше C в данном заказе. Это число можно вычислить из C = { c_k, ..., c₂, c₁ } с c_k > ... > c₂ > c₁ следующее. Из определения порядка следует, что для каждого k-комбинация S строго меньше чемC, есть уникальный индекся такой, что c_я отсутствует в S, пока c_k, ..., c_я+1 присутствуют в S, и никакое другое значение больше, чем c_я является. Поэтому можно сгруппировать эти k-комбинации S по возможным значениям 1, 2, ..., k из я, и подсчитайте каждую группу отдельно. Для данного значения я нужно включатьc_k, ..., c_я+1 в S, а остальные я элементы S должен быть выбран из c_я неотрицательные целые числа строго меньше, чем c_я; более того, любой такой выбор приведет к k-комбинации S строго меньше чемC. Количество возможных вариантов: ${ displaystyle { tbinom {c_ {i}} {i}}}$ , то есть количество комбинаций в группе я; общее количество k-комбинации строго меньше C тогда это

{ displaystyle { binom {c_ {1}} {1}} + { binom {c_ {2}} {2}} + cdots + { binom {c_ {k}} {k}},}

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

Нахождение k-комбинация по заданному номеру

Данная формула позволяет найти место в лексикографической упорядоченности данного k-комбинация сразу. Обратный процесс поиска k-комбинация в данном месте N требует немного больше работы, но, тем не менее, прост. По определению лексикографического порядка два k-комбинации, которые отличаются самым большим элементом c_k будут упорядочены в соответствии со сравнением этих самых больших элементов, из чего следует, что все комбинации с фиксированным значением их самого большого элемента являются смежными в списке. Причем наименьшее сочетание с c_k поскольку самый большой элемент ${ displaystyle { tbinom {c_ {k}} {k}}}$ , и у него есть c_я = я - 1 для всех я < k (для этой комбинации все термины в выражении, кроме ${ displaystyle { tbinom {c_ {k}} {k}}}$ равны нулю). Следовательно c_k это наибольшее число такое, что ${ Displaystyle { tbinom {c_ {k}} {k}} leq N}$ . Если k > 1 остальные элементы k-комбинация из k − 1-комбинация, соответствующая номеру ${ displaystyle N - { tbinom {c_ {k}} {k}}}$ в комбинаторной системе счисления степеней k − 1, и поэтому его можно найти, продолжая таким же образом для ${ displaystyle N - { tbinom {c_ {k}} {k}}}$ и k − 1 вместо N и k.

Пример

Предположим, кто-то хочет определить 5-комбинацию в позиции 72. Последовательные значения ${ displaystyle { tbinom {n} {5}}}$ за п = 4, 5, 6, ... равны 0, 1, 6, 21, 56, 126, 252, ..., из которых наибольшее, не превышающее 72, равно 56, для п = 8. Следовательно c₅ = 8, а остальные элементы образуют 4-комбинацию в позиции 72 − 56 = 16. Последовательные значения ${ displaystyle { tbinom {n} {4}}}$ за п = 3, 4, 5, ... равны 0, 1, 5, 15, 35, ..., из которых наибольшее, не превышающее 16, равно 15, для п = 6, поэтому c₄ = 6. Продолжая аналогично поиску 3-комбинации в позиции 16 − 15 = 1 можно найти c₃ = 3, который использует последнюю единицу; это устанавливает ${ displaystyle 72 = { tbinom {8} {5}} + { tbinom {6} {4}} + { tbinom {3} {3}}}$ , а остальные значения c_я будут максимальными с ${ displaystyle { tbinom {c_ {i}} {i}} = 0}$ , а именно c_я = я − 1. Таким образом, мы нашли 5-комбинацию {8, 6, 3, 1, 0}.

Пример национальной лотереи в Excel

Для каждого из ${ displaystyle { binom {49} {6}}}$ лотерейные комбинации c₁ < c₂ < c₃ < c₄ < c₅ < c₆ , есть номер списка N от 0 до ${ displaystyle { binom {49} {6}} - 1}$ который можно найти, добавив

{ displaystyle { binom {49-c_ {1}} {6}} + { binom {49-c_ {2}} {5}} + { binom {49-c_ {3}} {4}} + { binom {49-c_ {4}} {3}} + { binom {49-c_ {5}} {2}} + { binom {49-c_ {6}} {1}}.}

Предположим, вы хотите найти позицию результата 3,6,15,17,18,35 британской национальной лотереи в списке возможных результатов. Функция Excel COMBIN (49,6) покажет, что количество результатов равно 13983816. Теперь, если вы поместите числа 3,6,15,17,18,35 каждое в его ячейку и формулы COMBIN (49-3,6), COMBIN ( 49-6,5), COMBIN (49-15,4), COMBIN (49-17,3), COMBIN (49-18,2), 49−35 под каждым из них. Используйте ссылки на ячейки вместо фактических значений, фактические значения предоставляются для удобства чтения. Вы получите ряд чисел 9366819,962598,46376,4960,465,14. Их сложение покажет конкретную позицию 10381232. Обратите внимание, что вам не нужно использовать формулу COMBIN (49-35,1), чтобы получить 14. Вы можете получить ее только вычитанием 49-35. Также функция COMBIN не возвращает 0, если 49-X становится меньше 6. Вам нужно будет использовать IF с функцией ISNUMBER для преобразования #NUM! в 0.

Теперь обратная инженерия немного сложнее. Вы можете использовать 49 операторов IF в одной ячейке или использовать решатель, чтобы найти максимальный аргумент для результата COMBIN, который меньше или равен номеру позиции. Вместо этого давайте воспользуемся таблицей 6 на 49 и функцией ПОИСКПОЗ, где номер результирующей строки будет аргументом и номером шара. Если вы сделаете заголовки столбцов от 6 до 1 (B1: G1) в порядке убывания, а метки строк от 1 до 49 (A2: A50) в порядке возрастания (вертикальное возрастание в Excel означает, что числа растут сверху вниз). Затем, если вы заполните таблицу формулой COMBIN ($ A2, B $ 1), начиная с левого верхнего угла. Знаки $ будут гарантировать, что значения индекса всегда берутся из строки заголовка и столбца метки. Заменить # ЧИСЛО! с нулями. У вас должно получиться что-то вроде этого:

	6	5	4	3	2	11	0	0	0	0	0	12	0	0	0	0	1	23	0	0	0	1	3	34	0	0	1	4	6	45	0	1	5	10	10	56	1	6	15	20	15	67	7	21	35	35	21	78	28	56	70	56	28	89	84	126	126	84	36	910	210	252	210	120	45	1011	462	462	330	165	55	1112	924	792	495	220	66	12...49	13983816	1906884	211876	18424	1176	49

Теперь, если вы создадите новую строку из шести ячеек и заполните их формулами, которые найдут наибольшие значения в каждом столбце, которые меньше или равны номеру рассматриваемой позиции: первая ячейка с = ИНДЕКС (B2: B50, MATCH (10381232 , B2: B50)), остальные ячейки с

ИНДЕКС (C2: C50, ПОИСКПОЗ (10381232-СУММ (из предыдущих ячеек), C2: C50)) ... ИНДЕКС (G2: G50, ПОИСКПОЗ (10381232-СУММ (из предыдущих ячеек), G2: G50))

Это представит вам ряд значений, которые вы уже видели 9366819,962598,46376,4960,465,14Теперь в следующей строке первая ячейка write = 49-MATCH (10381232, B2: B50) и аналогично

= 49-ПОИСКПОЗ (10381232-9366819, C2: C50) ... = 49-ПОИСКПОЗ (10381232-9366819-962598-46376-4960-465, G2: G50)

Снова используйте ссылки на ячейки вместо фактических значений. Вам должны быть представлены оригинальные номера шаров 3,6,15,17,18,35.

Теперь вы можете сгенерировать новую комбинацию номеров лотереи из single = randbetween (1, combin (49,6)) или вы можете посмотреть номера позиций в списке предыдущих результатов, чтобы увидеть, есть ли тенденция.

Приложения

Можно использовать комбинаторную систему счисления для перечисления или обхода всех k-комбинации заданного конечного множества, но это очень неэффективный способ сделать это. Действительно, учитывая некоторые k-комбинации гораздо легче найти следующую комбинацию в лексикографическом порядке напрямую, чем преобразовать число в k-комбинация указанным выше способом. Чтобы найти следующую комбинацию, найдите наименьшее я ≥ 2, для которых c_я ≥ c_я-1+2 (если такого нет я, брать я = k+1); затем увеличить c_я−1 по одному и установить все c_j с j < я − 1 к их минимальной стоимости j − 1. Если k-комбинация представлена своим характеристический вектор, то есть как двоичное значение с k бит 1, то следующее такое значение может быть вычислено без какого-либо цикла с использованием поразрядной арифметики: C ++ функция продвинется Икс к этому значению или вернуть ложный:

// найти следующую k-комбинациюbool следующая_комбинация(беззнаковый длинный& Икс) // предполагаем, что x имеет форму x'01 ^ a10 ^ b в двоичной системе{  беззнаковый длинный ты = Икс & -Икс; // извлекаем крайний правый бит 1; и = 0'00 ^ a10 ^ b  беззнаковый длинный v = ты + Икс; // установить последний незавершенный бит 0 и очистить вправо; v = x'10 ^ a00 ^ b  если (v==0) // затем переполнение в v или x == 0    возвращаться ложный; // сигнал, что следующая k-комбинация не может быть представлена  Икс = v +(((v^Икс)/ты)>>2); // v ^ x = 0'11 ^ a10 ^ b, (v ^ x) / u = 0'0 ^ b1 ^ {a + 2}, и x ← x'100 ^ b1 ^ a  возвращаться истинный; // успешное завершение}

Это называется Госпер взломать;^[7]соответствующий код сборки был описан как элемент 175 в HAKMEM.

С другой стороны, возможность напрямую генерировать k-комбинация по индексу N есть полезные приложения. В частности, он позволяет генерировать случайные k-комбинация п-элемент установлен с использованием случайного целого числа N с ${ Displaystyle 0 Leq N <{ tbinom {п} {к}}}$ , просто преобразовав это число в соответствующее k-комбинация. Если компьютерной программе необходимо вести таблицу с информацией о каждом k-комбинация заданного конечного множества, вычисление индекса N связанная с комбинацией, позволит получить доступ к таблице без поиска.

Смотрите также

Факторная система счисления (также называемые факторадами)
Первоначальная система счисления