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

Генерация перестановок

Сначала рассмотрим случай, когда все элементы в последовательности различны.

var a:array[1..10] of integer; { последовательность заданных значений }
    n:integer; { количество элементов в множестве }
procedure gen(i:integer);
var j,t:integer;
begin
  if i>=n then { завершение рекурсии }
  begin
    { обработка полученной перестановки, например, печать }
    for j:=1 to n do
      write(' ',a[j]);
    writeln;
    exit;
  end;
  for j:=i to n do
  begin 
    { на i-е место ставим последовательно элементы с i-го по n-й }
    t:=a[i];
    a[i]:=a[j];
    a[j]:=t;
    gen(i+1);
  end;
  { после выполнения цикла на i-м месте стоит последний
    элемент исходной последовательны, остальные элементы
    смещены на одну позицию вправо,
    восстанавливаем исходное состояние последовательности }
  t:=a[i];
  for j:=i+1 to n do
    a[j-1]:=a[j];
  a[n]:=t;
end;

На 1-м уровне рекурсии происходит выбор из `n` вариантов для 1-го элемента перестановки, на 2-м – из `n-1` варианта для 2-го элемента, …, на `(n-1)`-м – из 2 вариантов для `(n-1)`-го элемента, на `n`-м – из одного варианта `n`-го элемента. Таким образом генерируется `n*(n-1)*…*2*1\ =\ n!` различных перестановок.

Если в последовательности могут встречаться одинаковые элементы, то установка на `i`-е место элемента, совпадающего с тем, который там уже был, не дает новой перестановки.
Поэтому цикл в подпрограмме gen можно изменить следующим образом:

  for j:=i to n do
  if (i=j) or (a[i]<>a[j]) then { добавленная строка }
  begin 
    { на i-е место ставим последовательно элементы с i-го по n-й }
    t:=a[i];
    a[i]:=a[j];
    a[j]:=t;
    gen(i+1);
  end;

Элементы в последовательности `a` должны быть упорядочены по возрастанию. При этом перестановки будут получаться в лексикографическом порядке.

Пример применения:
Разбор задачи 90. Реестр перестановок