Комбинаторная система счисления
-
Комбинаторная система счисления
- Соответствие между натуральными числами и k-комбинациями
- Комбинации представлены в виде убывающих последовательностей
- Числа, меньшие (n k), соответствуют всем k-комбинациям из {0, 1, …, n − 1}
- Соответствие не зависит от размера множества
-
Нахождение числа по k-комбинации
- Формула для нахождения числа по k-комбинации
- Жадный алгоритм для нахождения k-комбинации по числу
-
Применение комбинаторной системы счисления
- Быстрое вычисление k-комбинаций в лексикографическом порядке
- Генерация k-комбинаций из заданного набора
- Подсчет k-комбинаций для тестирования, отбора проб и анализа лотерейных игр
-
Порядок комбинаций
- Лексикографический порядок убывающей последовательности элементов
- Сравнение комбинаций по наибольшему элементу
-
Место комбинации в порядке
- Число, связанное с k-комбинацией, равно числу k-комбинаций, строго меньших, чем она
- Формула для нахождения индекса комбинации в списке
-
Нахождение k-комбинации для заданного числа
- Обратный процесс поиска k-комбинации по номеру
- Использование последовательных значений (n k) для нахождения наибольшего числа, не превышающего N
-
Пример
- Определение комбинации из 5 в позиции 72
- Нахождение остальных элементов комбинации
-
Пример национальной лотереи
- Поиск номера N для каждой лотерейной комбинации