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

Имеется n различных предметов. Сколько из них можно составить k-расстановок? При этом две расстановки считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке. Такие расстановки называют размещениями без повторений, а их число обозначают . При составлении k -размещений без повторений из n предметов нам надо сделать k выборов. На первом шаге можно выбрать любой из имеющихся n предметов. Если этот выбор уже сделан, то на втором шаге приходится выбирать из оставшихся n-1 предметов. На k -м шаге n-k-1 предметов. Поэтому по правилу произведения получаем, что число k -размещений без повторения из n предметов выражается следующим образом:

Например, при генерации всех размещений из 5 элементов по 3 в случае, когда сами элементы обозначены латинскими буквами А, B, C, D, E, нужно получить следующую последовательность, представленную для компактности в виде 10 строк, каждая из которых представляет все возможные сочетания из 3 букв первого элемента строки (первые элементы строк представляют все возможные сочетания из 5 букв по 3:

ABC ACB BAC BCA CAB CBA.

ABD …

ABE …

ACD …

ACE …

ADE …

BCD …

BCE …

BDE …

CDE CED DCE DEC ECD EDC