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

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

Число 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 максимальное с , затем возьмите c _k_{- 1} максимальное с , и так далее. Нахождение числа N , используя формулу выше, из k -комбинации ( c _k , ..., c ₂ , c ₁ ${\ Displaystyle {\ tbinom {c_ {k}} {k}} \ leq N}$ ${\ Displaystyle {\ tbinom {c_ {k-1}} {k-1}} \ leq N - {\ tbinom {c_ {k}} {k}}}$ ) также известен как «ранжирование», а противоположная операция (заданная жадным алгоритмом) как «снятие рейтинга»; эти операции известны под этими именами в большинстве систем компьютерной алгебры и в вычислительной математике . ^[2]^[3]

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

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

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

Комбинации заказов [ править ]

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

Чтобы гарантировать, что числа, представляющие k -комбинации {0, 1, ..., n - 1 }, меньше чисел, представляющих k- сочетания, не содержащиеся в {0, 1, ..., n - 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, существует уникальный индекс i такой, что c _i отсутствует в S , в то время как c _k , ..., c _{i +1} присутствуют в S , и никакое другое значение, превышающее c _{i, не} присутствует. Следовательно, можно сгруппировать эти k -комбинации S в соответствии с возможными значениями 1, 2, ..., k из i и подсчитать каждую группу отдельно. Для данного значения i необходимо включить c _k , ..., c _{i +1} в S , а оставшиесяI элементы S должны быть выбраны из гр _я неотрицательных целых чисел строго меньше , чем с _я ; кроме того , любой такой выбор будет приводить к K -combinations S строго меньше , чем C . Число возможных вариантов выбора равно количеству комбинаций в группе i ; общее количество k -комбинаций строго меньше, чем C, то ${\ displaystyle {\ tbinom {c_ {i}} {i}}}$

{\ 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 в} качестве наибольшего элемента , и она имеет c _i ${\ displaystyle {\ tbinom {c_ {k}} {k}}}$ = i - 1 для всех i < k (для этой комбинации все члены в выражении, кроме нуля). Следовательно, c _k - наибольшее число такое, что . Если k > 1, оставшиеся элементы k -комбинации образуют k - 1 -комбинацию, соответствующую числу в комбинаторной системе счисления степени k - 1 , и поэтому их можно найти, продолжая таким же образом для и k - 1. вместо N и k . ${\ displaystyle {\ tbinom {c_ {k}} {k}}}$ ${\ Displaystyle {\ tbinom {c_ {k}} {k}} \ leq N}$ ${\ displaystyle N - {\ tbinom {c_ {k}} {k}}}$ ${\ displaystyle N - {\ tbinom {c_ {k}} {k}}}$

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

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

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

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

{\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 -комбинацию указанным выше методом. Чтобы найти следующую комбинацию, найдите наименьшее i ≥ 2, для которого c _i ≥ c _{i − 1} +2 (если такого i нет , возьмите i = k +1); затем увеличиваем c _{i −1} на единицу и устанавливаем все c _jс j < i - 1 до их минимального значения j - 1 . Если k -комбинация представлена ее характеристическим вектором , то есть двоичным значением с k битами 1, то следующее такое значение может быть вычислено без какого-либо цикла с использованием побитовой арифметики: следующая функция C ++ продвинет x к этому значению или вернет ложь :

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

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

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

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

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

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

^ Прикладная комбинаторная математика , Под ред. EF Beckenbach (1964), стр. 27-30.
^ http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf
^ https://www.sagemath.org/doc/reference/sage/combinat/subset.html
^ Knuth, DE (2005), «Создание всех комбинаций и разделов», Искусство компьютерного программирования , 4, Fascicle 3, Addison-Wesley, pp. 5-6, ISBN 0-201-85394-9.
↑ Паскаль, Эрнесто (1887), Giornale di Matematiche , 25 , стр. 45-49
^ Маккаффри, Джеймс (2004), Создание m-го лексикографического элемента математической комбинации , Microsoft Developer Network
^ Knuth, DE (2009), «Побитовые приемы и методы», Искусство компьютерного программирования , 4, Fascicle 1, Addison-Wesley, p. 54, ISBN 0-321-58050-8

[1] Прикладная комбинаторная математика , Под ред. EF Beckenbach (1964), стр. 27-30.

[2] ttp://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf

[3] ttps://www.sagemath.org/doc/reference/sage/combinat/subset.html

[4] Knuth, DE (2005), «Создание всех комбинаций и разделов», Искусство компьютерного программирования , 4, Fascicle 3, Addison-Wesley, pp. 5-6, ISBN 0-201-85394-9.

[5] Паскаль, Эрнесто (1887), Giornale di Matematiche , 25 , стр. 45-49

[6] Маккаффри, Джеймс (2004), Создание m-го лексикографического элемента математической комбинации , Microsoft Developer Network

[7] Knuth, DE (2009), «Побитовые приемы и методы», Искусство компьютерного программирования , 4, Fascicle 1, Addison-Wesley, p. 54, ISBN 0-321-58050-8

[1]