Алгоритм порождения размещений

Так как размещения - это упорядоченные k -элементные подмножества множества из n элементов (упорядоченные сочетания из n no k), то алгоритм их порождения можно получить путем комбинации алгоритмов порождения сочетаний и перестановок.

Алгоритмы порождения композиций

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

Каждая композиция n из k частей при р_i >0 соответствует способу выбора (k -1)-элементного подмножества точек из n -1 точек разделения. Т.е. алгоритм порождения композиций n из k частей (р_i >0) сводится к генерации сочетаний из n -1 no k -1 и обращению их в данные композиции (см. табл. 2.1).

Аналогично алгоритм порождения композиции n из k частей при р_i ³0 сводится к генерации сочетаний из n + k -1 по k -1 и обращению их в соответствующие композиции.