Алгоритмы порождения сочетаний

Без ограничения общности можно полагать, что элементами множества являются целые числа от 1 да n.

Рассмотрим алгоритм порождения сочетаний в возрастающем лексикографическом порядке, т.е. в порядке, когда в каждом сочетании элементы расположены в порядке возрастания слева направо. Например, сочетания из шести элементов по три (), в возрастающем лексикографическом порядке запишутся следующим образом:

123 135 234 256

124 136 235 345

125 145 236 346

126 146 245 356

134 156 246 456

Сочетания в лексикографическом порядке можно порождать следующим образом. Начиная с сочетания (1,2,..., k), следующее сочетание находится просмотром текущего сочетания справа налево с тем, чтобы определить место самого правого элемента, который не достиг еще своего максимального значения. Этот элемент увеличивается на единицу, и всем элементам справа от него присваиваются новые наименьшие возможные значения как показано в алгоритме 4.

Эффективный метод порождения случайных сочетаний из n по k осуществляют случайные перестановки на первых k местах множества, например, такие, как в алгоритме 5. [5]