Как известно, возможное число вариантов перестановок из
элементов равно
, а это значит, что каждой перестановке можно поставить в соответствие код или номер, выражающийся натуральным числом
Поскольку элементами перестановки могут быть различные объекты: названия предметов, фамилии людей и т.п., то предварительно эти объекты всегда можно пронумеровать числами и в последующем оперировать ими как с элементами перестановки
, где
Программа генерирования перестановок построена на основании метода декодирования Бабаева А.А. [1].
Если организовать последовательное обращение к процедуре 2 с числами , то получим полное множество лексикографически отличающихся друг от друга перестановок.
Введем обозначения:
количество элементов перестановки;
Далее происходит обращение к процедуре 2 (алгоритм Бабаева А.А.) и генерируется перестановка для целого числа .
Процедура 2.
M1. Вычислить , где
– остаток от деления двух чисел.
Если , то вычислить
, где
— целая часть от деления, вычислить
и перейти к М1, иначе перейти к М2.
Если , вычислить
и перейти к М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.