29
правок
Изменения
Нет описания правки
Следующий алгоритм вычисляет эту сумму:
*<tex>\mathtt{numOfObject}</tex> {{---}} искомый номер комбинаторного объекта,
*<tex>\mathtt{a[1..n]}</tex> {{---}} данный комбинаторный обьект, состоящий из числовых представлений лексикографически упорядоченных элементов множества <tex>A</tex>,
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество комбинаторных объектов с префиксом от <tex>1</tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>,
'''int''' object2num(a: '''list<A>'''):
numOfObject = 0
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font> '''for''' j = <tex>A_{min}</tex> 1 '''to''' предшествующий a[i] элемент '''do''' - 1 <font color=green>// перебираем элементы, в лексикографическом порядке меньшие рассматриваемого</font>
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место
numOfObject += d[i][j]
'''return''' numOfObject
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается.
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.
'''int''' bitvector2num(bitvector: '''list<int>'''):
numOfBitvector = 0
'''for''' i = 1 '''to''' n '''do'''
'''if''' bitvector[i] == 1
numOfBitvector += pow(2 <tex>\ll</tex> , n-i-1)
'''return''' numOfBitvector
'''int''' permutation2num(a: '''list<int>'''):
numOfPermutation = 0
'''for''' i = 1 '''to''' n '''do''' <font color=green>// <tex>n</tex> {{---}} количество элементов в перестановке</font> '''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font>
'''if''' was[j] == ''false'' <font color=green>// если элемент <tex>j</tex> ранее не был использован</font>
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font>
== Сочетания ==
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <texdpi=140>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <texdpi=140>$$\sum\limits^{val_1-1}_{i=1} {\binom{n-i}{k-1}}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <texdpi=140>$$\sum\limits^{val_2-1}_{i=val_1+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>,
'''int''' choose2num(choose: '''list<int>'''):
numOfChoose = 0
'''for''' i = 1 '''to''' K '''do''' '''for''' i = choose[i - 1] + 1 '''to''' choose[i] - 1 '''do'''
numOfChoose += C[N - j][K - i]
'''return''' numOfChoose
