Advertisement
algorithmuscanorj

Schoolar farewell task #1

Dec 18th, 2012
402
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Pascal 4.05 KB | None | 0 0
  1. program PermutationsWithoutRepetitions;
  2.  
  3. (*
  4.  
  5.   USAGE:
  6.   -----
  7.  
  8.    i] Compile this sourcecode and place the executable in a proper location.
  9.       (It is strongly suggested to use the FPC compiler. Please visit: freepascal.org)
  10.    
  11.   ii] Create a empty file called "permworep_idata.txt" and fill it just with
  12.       a sigle zero. Save it in the same directory for the executable mentioned
  13.       in [i] and ensure that there will be granted read-write permissions
  14.       for this program during its execution.
  15.      
  16.  iii] For obtaining the 10! permutations for the first 10 non-negative integers
  17.       enumerated starting from zero, call the program passing "9" as its unique parameter.
  18.       (This is due zero is the first digit in every positional number system)
  19.      
  20.       Instead of using double byte numbers like 11 or 16, use the letter representing
  21.       it as digit in a base greater than the decimal. The progrma is theoretically
  22.       limited up to 36 digits enumerated from zero.
  23.  
  24.   iv] Depending on the resources available during the execution, this program might not
  25.       work properly as expected, being interrumped or crashing for example when used to
  26.       computed sets of permutations greater than 10 ("a" letter).
  27.  
  28.  Written by R. J. Cano, <aallggoorriitthhmmuuss@gmail.com> on Dec 9th 2012.
  29.  
  30.  Observation: There exists better known algorithms/methods for computing pemutations.
  31.  The present program is merely another one more among the possible implementations for
  32.  doing such jobs.
  33.  
  34.  See for example the entry A055881 at OEIS.org, specifically the comment by Joerg Arndt.
  35.  
  36.  The purpose on writing this program was to serve as ilustration for the algorithm known
  37.  as Steinhaus-Jhonson-Trotter, and additionally about how to do these thing using the
  38.  hard disk instead the primary memory.
  39.  
  40.  Important: The present program is released under the terms
  41.             of the GNU General Public License 3.0 and it goes
  42.             without any warranty whatsoever.
  43.  
  44. *)
  45.  
  46. type
  47.  my_string=string[15]; (* Mem. saving measure: Limit only 16 bytes per string. Up to the first 15! permutations only *)
  48.  
  49. const
  50.  basename:string='permworep';
  51.  digit:array [0..35] of char=
  52.    ('0','1','2','3','4','5','6','7','8','9',
  53.     'a','b','c','d','e','f','g','h','i','j',
  54.     'k','l','m','n','o','p','q','r','s','t',
  55.     'u','v','w','x','y','z');
  56. var
  57.  f_input,
  58.  f_output : text;
  59.  input,
  60.  output,
  61.  request:my_string;
  62.  size_i,
  63.  size_o,
  64.  index_a,
  65.  index_b:byte;
  66.  index_c,
  67.  dir:shortint;
  68.  insert:char;
  69.  
  70. function f(x:char):byte;
  71. var ans:byte;
  72. begin
  73.   if (x in ['a'..'z']) then begin
  74.     ans:=10+ord(x)-ord('a');
  75.   end else if (x in ['0'..'9']) then begin
  76.     ans:=ord(x)-ord('0');
  77.   end else begin
  78.     ans:= 255;
  79.   end;
  80.   f:=ans;
  81. end;
  82.  
  83. begin
  84.  if (paramcount = 1) then begin
  85.   request:=paramstr(1);
  86.   size_o:=f(request[length(request)])+1;
  87.   assign(f_input,basename+'_idata.txt');
  88.   assign(f_output,basename+'_odata.txt');
  89.   reset(f_input);
  90.   readln(f_input,input);
  91.   close(f_input);
  92.   size_i:=f(input[length(input)])+1;
  93.   while (size_o > size_i) do begin
  94.    dir:=-1;
  95.    assign(f_input,basename+'_idata.txt');
  96.    assign(f_output,basename+'_odata.txt');
  97.    reset(f_input);
  98.    rewrite(f_output);
  99.    insert:=digit[size_i];
  100.    while (not eof(f_input)) do begin
  101.      readln(f_input,input);
  102.      for index_a:= 0 to size_i do begin
  103.        output:='';
  104.        index_c:=-1;
  105.        for index_b:= 0 to size_i do begin
  106.          if ((dir=-1) and (index_a+index_b=size_i)) then begin
  107.            output:=output+digit[size_i];
  108.          end else if ((dir=1) and (index_a=index_b)) then begin
  109.            output:=output+digit[size_i];
  110.          end else begin
  111.            if (index_c=size_i-1) then index_c:=-1;
  112.            index_c:=index_c+1;
  113.            output:=output+input[index_c+1];
  114.          end;
  115.        end;
  116.        writeln(f_output,output);
  117.      end;
  118.      dir:= dir*(-1);
  119.    end;
  120.    close(f_input);
  121.    close(f_output);
  122.    erase(f_input);
  123.    assign(f_input,'tmp');
  124.    rename(f_output,basename+'_idata.txt');
  125.    size_i:= size_i + 1;
  126.   end;
  127.  end;
  128. end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement