Advertisement
algorithmuscanorj

pizza hut cheff hunting mices

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