Перестановки (рекурсивный алгоритм)

Задача та же, что в пункте 1.2. Опишем рекурсивную процедуру Generate(k), предъявляющую все перестановки чисел 1,...,N, у которых фиксировано начало X[1],X[2],...,X[k]. После выхода из процедуры массив X будут иметь то же значение, что перед входом (это существенно!). Понятно, что при k=N мы снова имеем только тривиальное решение - саму перестановку. При k<N будем сводить задачу к k+1:

procedure Generate(k:byte); var i,j:byte; procedure Swap(var a,b:byte); var c:byte; begin c:=a;a:=b;b:=c end; begin if k=N then begin for i:=1 to N do write(X[i]);writeln end else for j:=k+1 to N do begin Swap(X[k+1],X[j]); Generate(k+1); Swap(X[k+1],X[j]) end

end;

Основная программа:

program PerestanovkiRecursion; type Pere=array [byte] of byte; var N,i,j:byte; X:Pere; procedure Generate(k:byte);............... begin write('N=');readln(N); for i:=1 to N do X[i]:=i; Generate(0) end.

Чтобы до конца разобраться в этой непростой программе, советуем выполнить ее на бумаге при N=3. Обратите внимание, что порядок вывода перестановок не будет лексикографическим!