29
правок
Изменения
Нет описания правки
numOfObject = 0
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font>
'''for''' j = <tex>A_{min}</tex> '''to''' предшествующий a[i] элемент '''do''' <font color=green>// перебираем элементы, в лексикографическом порядке меньшие рассматриваемого</font>
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место
numOfObject += d[i][j]
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов меньше рассматриваемого можно упростить до проверки элемента на равенство <tex>1</tex>:
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,
== Сочетания ==
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex>$$\sum_sum\limits^{val_1-1}_{i=1}^{val_1-1} \binom{n-i}{k-1}}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex>$$\sum_sum\limits^{val_2-1}_{i=val_1+1}^{val_2-1} \binom{n-i}{k-2}}$$</tex>. Аналогично продолжаем по следующим позициям:
*<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания,
*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,
