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

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

Рассмотрим алгоритм порождения сочетаний в возрастающем лексикографическом порядке, т.е. в порядке, когда в каждом сочетании элементы расположены в порядке возрастания слева направо. Например, сочетания из шести элементов по три ( ) в возрастающем лексикографическом порядке запишутся следующим образом: 123, 124, 125, 126, 134, 135, 136, 145, 146, 156, 234, 235, 236, 245, 246, 256, 345, 346, 356, 456.

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

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