Advertisement
algorithmuscanorj

Biker mice

Dec 22nd, 2012
410
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. (*
  2.  
  3.  Revision: Dec 22 2012 New age dawn! :-D
  4.  
  5.     -Minor corrections made inside the comments for clarity and readability.
  6.     -A not used variable detected and deleted.
  7.    
  8.  For example if you want to obtain the "natural" permutations for base-13, this
  9.  is for the decimal digits and a,b,c notice that c=12 regarded as digit in the
  10.  conventional notation, but since we started here to count from zero, each latin
  11.  alphabet letter have its conventional value +1 when it is used for counts.
  12.  
  13.  Then follow the usual instructions given below (please read them), and call:
  14.  
  15.   --------------------------------------------------------[Linux Shell example]
  16.  
  17.   gandalf@rivendell@sh$ permworep c
  18.  
  19.   ----------------------------------------------------------------------------
  20.  
  21.   Written on my host machine:
  22.  
  23.   * 32-bit Intel Atom with 160Gb Hdd 1Gb Ram,
  24.   * Slackware GNU Linux distro version 14
  25.   * Free Pascal Compiler 2.6.2
  26.  
  27.   Formerly was http://pastebin.com/ZCLc63XG... all bogus bugs apparently fixed.
  28.  
  29. *)
  30.  
  31. program PermutationsWithoutRepetitions;
  32.  
  33. (*
  34.  
  35.   USAGE:
  36.   -----
  37.  
  38.    i] Compile this sourcecode and place the executable in a proper location.
  39.       (It is strongly suggested to use the FPC compiler. Please visit:
  40.       freepascal.org)
  41.    
  42.   ii] Create a empty file called "permworep_idata.txt" and fill it just with
  43.       a sigle zero. Save it in the same directory for the executable mentioned
  44.       in [i] and ensure that there will be granted read-write permissions
  45.       for this program during its execution.
  46.      
  47.  iii] For obtaining the 10! permutations for the first 10 non-negative integers
  48.       enumerated starting from zero, call the program passing "9" as its unique
  49.       parameter.
  50.      
  51.       (This is due zero is the first digit in every positional number system)
  52.      
  53.       Instead of using double byte numbers like 11 or 16, use the letter
  54.       representing it as digit in a base greater than the decimal. The program
  55.       is theoretically limited up to 36 digits enumerated from zero.
  56.  
  57.   iv] Depending on the resources available during the execution, this program
  58.       might not work properly as expected, being interrumped or crashing for
  59.       example when used to computed sets of permutations greater than 10 ("a"
  60.       letter).
  61.  
  62.  Written by R. J. Cano, <aallggoorriitthhmmuuss@gmail.com> on Dec 9th 2012.
  63.  
  64.  Observation: There exists better known algorithms/methods for computing
  65.  pemutations. The present program is merely another one more among the possible
  66.  implementations for doing such jobs.
  67.  
  68.  See for example the entry A055881 at OEIS.org, specifically the comment
  69.  by Joerg Arndt.
  70.  
  71.  The purpose on writing this program was to serve as ilustration for the
  72.  algorithm known as Steinhaus-Jhonson-Trotter, and additionally about how
  73.  to do these thing using the hard disk instead the primary memory.
  74.  
  75.  Important: The present program is released under the terms
  76.             of the GNU General Public License 3.0 and it goes
  77.             without any warranty whatsoever.
  78.  
  79. *)
  80.  
  81. type
  82.  my_string=string[15];
  83.  (* Mem. saving measure: Limit only 16 bytes per string.
  84.     Up to the first 15! permutations only *)
  85.  
  86. const
  87.  basename:string='permworep';
  88.  digit:array [0..35] of char=
  89.    ('0','1','2','3','4','5','6','7','8','9',
  90.     'a','b','c','d','e','f','g','h','i','j',
  91.     'k','l','m','n','o','p','q','r','s','t',
  92.     'u','v','w','x','y','z');
  93. var
  94.  f_input,
  95.  f_output : text;
  96.  input,
  97.  output,
  98.  request:my_string;
  99.  size_i,
  100.  size_o,
  101.  index_a,
  102.  index_b:byte;
  103.  index_c,
  104.  dir:shortint;
  105.  
  106. function f(x:char):byte;
  107. var ans:byte;
  108. begin
  109.   if (x in ['a'..'z']) then begin
  110.     ans:=10+ord(x)-ord('a');
  111.   end else if (x in ['0'..'9']) then begin
  112.     ans:=ord(x)-ord('0');
  113.   end else begin
  114.     ans:= 255;
  115.   end;
  116.   f:=ans;
  117. end;
  118.  
  119. begin
  120.  if (paramcount = 1) then begin
  121.   request:=paramstr(1);
  122.   size_o:=f(request[length(request)])+1;
  123.   assign(f_input,basename+'_idata.txt');
  124.   assign(f_output,basename+'_odata.txt');
  125.   reset(f_input);
  126.   readln(f_input,input);
  127.   close(f_input);
  128.   size_i:=f(input[length(input)])+1;
  129.   while (size_o > size_i) do begin
  130.    dir:=-1;
  131.    assign(f_input,basename+'_idata.txt');
  132.    assign(f_output,basename+'_odata.txt');
  133.    reset(f_input);
  134.    rewrite(f_output);
  135.    while (not eof(f_input)) do begin
  136.      readln(f_input,input);
  137.      for index_a:= 0 to size_i do begin
  138.        output:='';
  139.        index_c:=-1;
  140.        for index_b:= 0 to size_i do begin
  141.          if ((dir=-1) and (index_a+index_b=size_i)) then begin
  142.            output:=output+digit[size_i];
  143.          end else if ((dir=1) and (index_a=index_b)) then begin
  144.            output:=output+digit[size_i];
  145.          end else begin
  146.            if (index_c=size_i-1) then index_c:=-1;
  147.            index_c:=index_c+1;
  148.            output:=output+input[index_c+1];
  149.          end;
  150.        end;
  151.        writeln(f_output,output);
  152.      end;
  153.      dir:= dir*(-1);
  154.    end;
  155.    close(f_input);
  156.    close(f_output);
  157.    erase(f_input);
  158.    assign(f_input,'tmp');
  159.    rename(f_output,basename+'_idata.txt');
  160.    size_i:= size_i + 1;
  161.   end;
  162.  end;
  163. end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement