Как известно, возможное число вариантов перестановок из 
элементов равно 
, а это значит, что каждой перестановке можно поставить в соответствие код или номер, выражающийся натуральным числом 
Поскольку элементами перестановки могут быть различные объекты: названия предметов, фамилии людей и т.п., то предварительно эти объекты всегда можно пронумеровать числами 
и в последующем оперировать ими как с элементами перестановки 
, где 
Программа генерирования перестановок построена на основании метода декодирования Бабаева А.А. [1].
Если организовать последовательное обращение к процедуре 2 с числами 
, то получим полное множество лексикографически отличающихся друг от друга перестановок.
Введем обозначения:
количество элементов перестановки;
.
Далее происходит обращение к процедуре 2 (алгоритм Бабаева А.А.) и генерируется перестановка для целого числа 
.
Процедура 2.
Начало. Ввести 
Вычислить k
.
M1. Вычислить 
, где 
– остаток от деления двух чисел.
Если 
, то вычислить 
, где 
— целая часть от деления, вычислить 
и перейти к М1, иначе перейти к М2.
M2. Вычислить 
.
Если 
, вычислить 
и перейти к М2, иначе вывести перестановку 
Конец.
Текст программы генерации перестановок на Delphi
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,Dialogs, StdCtrls, Grids, ComCtrls;
type
TForm1 = class(TForm)
GroupBox2: TGroupBox;
StringGrid1: TStringGrid;
Button1: TButton;
Edit2: TEdit;
Label2: TLabel;
Label3: TLabel;
Label1: TLabel;
Edit1: TEdit;
StatusBar1: TStatusBar;
procedure FormCreate(Sender: TObject);
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
mas=array[1..99] of Integer;
Procedure perestan(N:Integer; nmal:Integer; var per:mas);
function fak(N: Integer): Integer;
var
Form1: TForm1;
V: Integer;
implementation
{$R *.dfm}
function fak(N: Integer): Integer;
begin;
if((N=0)or(N=1)) then Result:=1 else Result:=N*fak(N-1);
end;
Procedure perestan(N:Integer; nmal:Integer; var per:mas);
var
J,X : mas;
str1 : TStringList;
f,g : TextFile;
I,K,M,N2,N11,N3 : Integer;
i1,i2 : Integer;
label M1, M2;
begin
str1:=TStringList.Create;
k:=N; for i:=1 to N do J[i]:=i;
for i:=1 to N do Str1.Add(IntToStr(i));
M1:
m:=N-k+1;
x[k]:=nmal mod m;
if k>1 then
begin
nmal:=trunc(nmal/m);
k:=k-1;
goto M1;
end
else
begin
M2:
i:=x[k]+1;
x[k]:=StrToInt(str1[i-1]);
if k begin
for i1:=1 to str1.Count do
begin
if str1[i1-1]=str1[i-1] then
begin
str1.Delete(i1-1); break;
end;
end;
k:=k+1;
Goto M2;
end
else begin for i1:=1 to N do per[I1]:=X[I1]; end;
end;
end;
procedure TForm1.Button1Click(Sender: TObject);
Var
i,j:Integer;
per:mas;
f:TextFile;
i9,j9,N:Integer;
begin
//Число перестановок V
V:=fak(StrToInt(Edit1.Text));
Edit2.Text:=IntToStr(V);
StringGrid1.ColCount:=StrToInt(Edit1.Text)+1;
StringGrid1.RowCount:=V+1;
N:=StrToInt(Edit1.Text);
AssignFile(f,'Perestanovki.txt');
Rewrite(f);
Writeln(f,'Количество элементов=',Edit1.Text);
Writeln(f,'Количество перестановок=',Edit2.Text);
Writeln(f);
Writeln(f,'ПЕРЕСТАНОВКИ:');
Writeln(f,'=============');
for i := 1 to V do
Begin
Write(f,i:12,'. ');
perestan(N, i-1, per);
for j := 1 to N do
Begin
if N Write(f,per[j]:3,' ');
End;
Writeln(f);
End;
CloseFile(f);
ShowMessage('Выполнено!');
end;
procedure TForm1.FormCreate(Sender: TObject);
var
j:Integer;
begin
for j := 1 to 10000 do
begin
StringGrid1.Cells[j,0]:=IntToStr(j);
StringGrid1.Cells[0,j]:=IntToStr(j);
end;
end;
end.
Результаты сохраняются в текстовый файл «Perestanovki.txt» и выводятся в программе в компоненту StringGrid. Следует иметь в виду, что количество строк, располагаемых в компоненте StringGrid не может превышать 1048560, поэтому в компоненту выводятся перестановки только для тех заданий, в которых количество элементов перестановки менее 10.
Фрагмент листинга результатов работы программы:
Количество элементов=9
Количество перестановок=362880
ПЕРЕСТАНОВКИ:
=============
1. 1 2 3 4 5 6 7 8 9
2. 1 2 3 4 5 6 7 9 8
3. 1 2 3 4 5 6 8 7 9
4. 1 2 3 4 5 6 8 9 7
5. 1 2 3 4 5 6 9 7 8
6. 1 2 3 4 5 6 9 8 7
7. 1 2 3 4 5 7 6 8 9
8. 1 2 3 4 5 7 6 9 8
9. 1 2 3 4 5 7 8 6 9
10. 1 2 3 4 5 7 8 9 6
11. 1 2 3 4 5 7 9 6 8
12. 1 2 3 4 5 7 9 8 6
13. 1 2 3 4 5 8 6 7 9
14. 1 2 3 4 5 8 6 9 7
15. 1 2 3 4 5 8 7 6 9
16. 1 2 3 4 5 8 7 9 6
17. 1 2 3 4 5 8 9 6 7
18. 1 2 3 4 5 8 9 7 6
19. 1 2 3 4 5 9 6 7 8
20. 1 2 3 4 5 9 6 8 7
21. 1 2 3 4 5 9 7 6 8
22. 1 2 3 4 5 9 7 8 6
23. 1 2 3 4 5 9 8 6 7
24. 1 2 3 4 5 9 8 7 6
25. 1 2 3 4 6 5 7 8 9
26. 1 2 3 4 6 5 7 9 8
27. 1 2 3 4 6 5 8 7 9
28. 1 2 3 4 6 5 8 9 7
29. 1 2 3 4 6 5 9 7 8
30. 1 2 3 4 6 5 9 8 7
31. 1 2 3 4 6 7 5 8 9
32. 1 2 3 4 6 7 5 9 8
33. 1 2 3 4 6 7 8 5 9
34. 1 2 3 4 6 7 8 9 5
35. 1 2 3 4 6 7 9 5 8
36. 1 2 3 4 6 7 9 8 5
37. 1 2 3 4 6 8 5 7 9
Список литературы
1. Бабаев А.А. Процедуры кодирования и декодирования перестановок. -Кибернетика, АН УССР, 1984, №6, с.75-76.
