Сочетание - это выбор из N предметов нескольких (M), причем порядок не важен.
Из курса комбинаторики известно, что число сочетаний из N по M равно N!/(M! * (N - M)!)
Для примера, всего 10 сочетаний из 5 по 3:
Здесь снова приходит на помощь переход от одного сочетания к другому.
Опять же будем записывать сочетания в лексикографическом порядке.
Пусть текущее сочетание из 6 по 4 (в данном варианте последнее сочетние -
(3, 4, 5, 6)) будет (1, 2, 3, 6).
Найдем с конца числа, которые не "последние" на своих местах
(здесь 6 - последнее, а 3, 2 и 1 - нет). Находим первый индекс i, который
удовлетворяет этим условиям. Увеличим на 1 элемент с индексом i. получим (1, 2, 4, 6).
Для хвоста сочетания переносим предыдущие числа, увеличенные на 1.
В данном примере, i = 3. Перенос чисел даст (1, 2, 4, 5) - переносим
только 4-й элемент с третьего (4 + 1 = 5)
Const MaxN = 100; { Максимальное число элементов в множестве }
Var
Mas: Array[1 .. MaxN] Of Longint; { Текущее сочетание }
N, M: Longint;
I, J: Longint;
Procedure WriteComp; { Печать текущего сочетания }
Var I: Longint;
Begin
For I := 1 To M Do Write(Mas[I], ' ');
Writeln;
End;
Begin
ReadLn(N, M);
For I := 1 To M Do Mas[I] := I; { Заполняем сочетание числами от 1 до M }
While (True) Do
Begin
WriteComp; { Выводим сочетание }
I := M;
While (I > 0) And (Mas[I] = N - M + I) Do Dec(I);
If I = 0 Then Break; { Если все числа - последние, то все сочетания сгенерированы }
Inc(Mas[I]); { Увеличиваем на 1 найденный не последний элемент }
For J := I + 1 To M Do Mas[J] := Mas[J - 1] + 1; { Переносим хвост }
End;
End.
