29
правок
Изменения
→Сочетания
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex>C_n^k</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex>$$\sum_{i=1}^{val_1-1} C_{n-i}^{k-1}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex>$$\sum_{i=val_1+1}^{val_2-1} C_{n-i}^{k-2}$$</tex>. Аналогично продолжаем по следующим позициям:
*<tex>numOfChoose</tex> {{---}} искомый номер сочетания.
*<tex>choose[1..K]</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, из технических соображений припишем ноль в начало сочетания: <tex>choose[0] = 0</tex>.
*<tex>C[n][k]</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>C[n][0] = 1</tex>.
