2. Комбинаторные объекты

Генерация сочетаний

Количество вариантов выбора `k` элементов из `n` значений равно `C_n^k\ =\ {n!}/{k!*(n-k)!}`.

За основу генератора сочетаний можно взять генератор подмножеств, так как фактически сочетание – это подмножество из `k` элементов:

var a:array[1..20] of integer;
    k,n:integer;
    b:array[1..20] of boolean;
procedure gen(i,m:integer);
var j:integer;
begin
  if i>n then
  begin
    { обработка полученного сочетания, например, печать }
    for j:=1 to n do
      if b[j] then
        write(' ',a[j]);
      writeln;
    exit;
  end;
  if n-i>=k-m then { можно пропустить i-й элемент }
  begin
    b[i]:=false;
    gen(i+1,m);
  end;
  if m<k then { можно взять i-й элемент }
  begin
    b[i]:=true;
    gen(i+1,m+1);
  end;
end;

Вызов подпрограммы в основной программе выполняется так: gen(1,0);
Вторым аргументом в подпрограмме указывается текущее количество в подмножестве.

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

Пример применения:
Разбор задачи 1201. Подарки