Prosty generator permutacji

1

Z nudów napisałem prosty generator permutacji:

Uses Windows, Classes, SysUtils;
Type TStringArray = PShortString;

Var Generated, ToBeGenerated: uint64;
    OutputFile              : TextFile;
    InputSize               : uint8;

Type TStatusThread = Class(TThread)
                      Protected
                       Procedure Execute; override;
                      End;

(* TStatusThread.Execute *)
Procedure TStatusThread.Execute;
Var PrevGenerated, PerSecond: uint64;
Begin
 FreeOnTerminate := True;
 PrevGenerated   := Generated;

 While (not Terminated) Do
 Begin
  PerSecond := Generated-PrevGenerated;
  if (PerSecond = 0) Then
   Inc(PerSecond); // just to avoid div by zero in line below

  Writeln(Round(Generated/ToBeGenerated * 100), '% done (', Generated, ' of ', ToBeGenerated, '; ', PerSecond, '/sec; estimated finish time: ', (ToBeGenerated-Generated) div PerSecond, ' sec)');
  PrevGenerated := Generated;
  Sleep(1000);

  if (Generated >= ToBeGenerated) Then
   Terminate;
 End;
End;

(* Generate *)
Procedure Generate(Tab: TStringArray; const N, K: uint64);
Var I  : Integer;
    Tmp: ShortString;
Begin
 if (K = N) and (N = InputSize-1) Then
 Begin
  For I := 0 To N Do
  Begin
   Write(OutputFile, Tab[I]);
   if (I < N) Then
    Write(OutputFile, ' ');
  End;

  Writeln(OutputFile);
  Inc(Generated);
 End Else
 Begin
  Tmp := Tab[K];

  For I := K To N Do
  Begin
   Tab[K] := Tab[I];
   Tab[I] := Tmp;
   Generate(Tab, N, K+1);
   Tab[I] := Tab[K];
   Tab[K] := Tmp;
  End;
 End;
End;

(* Factorial *)
Function Factorial(I: uint8): uint64;
Begin
 Result := 1;

 For I := 1 To I Do
  Result *= I;
End;

// -------------------------------------------------------------------------- //
Var Input              : TStringArray;
    Time, EstimatedSize: uint64;
    I                  : Integer;
Begin
 Writeln('Simple permutation generator by Patryk Wychowaniec');
 Writeln;

 if (ParamCount < 2) Then // error: invalid args
 Begin
  Writeln('Use:');
  Writeln(ExtractFileName(ParamStr(0)), ' output_file elements_to_permutate');
  Writeln;
  Writeln('Eg.: ', ExtractFileName(ParamStr(0)), ' output.txt a b c d');
  Halt;
 End;

 InputSize := ParamCount-1;
 Input     := AllocMem(sizeof(PShortString)*InputSize);

 // parse elements to be permutated
 For I := 2 To ParamCount Do
  Input[I-2] := ParamStr(I);

 Generated     := 0;
 ToBeGenerated := Factorial(InputSize);

 Writeln('Output file: ', ParamStr(1));
 Writeln;

 Writeln('Elements to permutate:');
 For I := 0 To InputSize-1 Do
  Writeln('[', I, '] = ', Input[I]);

 // calculate estimated size
 EstimatedSize := 0;
 For I := 0 To InputSize-1 Do
  EstimatedSize += Length(Input[I])+uint64(I < InputSize-1);

 EstimatedSize *= ToBeGenerated + Length(LineEnding);
 EstimatedSize := EstimatedSize div 1024 div 1024;

 // display some info
 Writeln;
 Writeln('Permutations to be generated: ', InputSize, '! = ', ToBeGenerated);
 Writeln('Estimated output file size  : ', EstimatedSize, ' MB');
 Writeln;

 Time := GetTickCount;

 // open output file for writing
 Writeln('-> begin');
 AssignFile(OutputFile, ParamStr(1));
 Try
  Rewrite(OutputFile);
  TStatusThread.Create(False); // create status thread
  Generate(Input, InputSize-1, 0); // begin to permutate
 Finally
  Flush(OutputFile); // flush output...
  CloseFile(OutputFile); // ...and close it
 End;

 Time := GetTickCount - Time;

 Writeln('-> done in ', Time div 1000, ' seconds');
End.

Przykład:
ss.png

Wrzucam to bardziej w celach "może komu kiedyś się przyda", aniżeli jako-tako do oceny kodu (140 linijek, to nawet nie ma co oceniać :P) ;)


Jako załącznik wrzuciłem build dla 32-bitowego Windowsa wykonany we FPC 2.6.3.
0

Wydajność trochę niska? Dawno temu jak poznawałem Javę i nie znałem jeszcze słówka "permutacja" napisałem coś takiego: http://4programmers.net/Forum/Algorytmy/193283-wydajnosc_mojego_algorytmu_generujacego_kombinacje_znakow, dziś właśnie dodałem jeszcze zapisywanie do pliku i ok. 5 000 000 wyników/s, z Twojego programu poniżej 500 000/s
Wrzucę później nowszą wersję. Bo tam takie kwiatki jak dopisywanie do stringa za pomocą +=..

0

Hm, Ty chyba masz coś z lekka innego.
Mój generuje permutacje zbioru w taki sposób:

Wejście:
[0] = a
[1] = b
[2] = c

Wyjście:
a b c
a c b
b a c
b c a
c b a
c a b

Podczas gdy ten Twój z tego co zauważyłem to takie coś:

a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc
...

1 użytkowników online, w tym zalogowanych: 0, gości: 1