Эффективный алгоритм и программа генерации перестановок

perestanКак известно, возможное число вариантов перестановок из clip_image002 элементов равно clip_image004, а это значит, что каждой перестановке можно поставить в соответствие код или номер, выражающийся натуральным числом clip_image006

Поскольку элементами перестановки могут быть различные объекты: названия предметов, фамилии людей и т.п., то предварительно эти объекты всегда можно пронумеровать числами clip_image008 и в последующем оперировать ими как с элементами перестановки clip_image010, где clip_image012

Программа генерирования перестановок построена на основании метода декодирования Бабаева А.А. [1].

Если организовать последовательное обращение к процедуре 2 с числами clip_image014, то получим полное множество лексикографически отличающихся друг от друга перестановок.

Введем обозначения:

clip_image016количество элементов перестановки;

clip_image018.

Далее происходит обращение к процедуре 2 (алгоритм Бабаева А.А.) и генерируется перестановка для целого числа clip_image020.

Процедура 2.

Начало. Ввести clip_image022

Вычислить kclip_image024.

M1. Вычислить clip_image026, где clip_image028 – остаток от деления двух чисел.

Если clip_image030, то вычислить clip_image032, где clip_image034— целая часть от деления, вычислить clip_image036 и перейти к М1, иначе перейти к М2.

M2. Вычислить clip_image038.

Если clip_image040, вычислить clip_image042 и перейти к М2, иначе вывести перестановку clip_image044

Конец.

Текст программы генерации перестановок на 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.

Александр Малыгин

Объект обсуждения - программное обеспечение для выполнения автоматизированного конструкторского и технологического проектирования, разработки управляющих программ, вопросы, связанные с разработкой прикладных САПР.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *