SHOW:
|
|
- or go back to the newest paste.
| 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 |
| 3 | + | Revision: Dec 22 2012 New age dawn! :-D |
| 4 | - | notice that c=12 regarded as digit in the conventional notation, but since we started here to count from zero, each |
| 4 | + | |
| 5 | - | latin alphabet letter have its conventional value +1 when it is used for counts. |
| 5 | + | -Minor corrections made inside the comments for clarity and readability. |
| 6 | -A not used variable detected and deleted. | |
| 7 | - | Then follow the usual instructions given below (please read them), and call: |
| 7 | + | |
| 8 | For example if you want to obtain the "natural" permutations for base-13, this | |
| 9 | - | -------------------------------------------------------------[Linux Shell example] |
| 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 | - | ------------------------------------------------------------- |
| 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 | - | (It is strongly suggested to use the FPC compiler. Please visit: freepascal.org) |
| 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 | - | enumerated starting from zero, call the program passing "9" as its unique parameter. |
| 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 | - | Instead of using double byte numbers like 11 or 16, use the letter representing |
| 44 | + | |
| 45 | - | it as digit in a base greater than the decimal. The progrma is theoretically |
| 45 | + | |
| 46 | - | limited up to 36 digits enumerated from zero. |
| 46 | + | |
| 47 | iii] For obtaining the 10! permutations for the first 10 non-negative integers | |
| 48 | - | iv] Depending on the resources available during the execution, this program might not |
| 48 | + | enumerated starting from zero, call the program passing "9" as its unique |
| 49 | - | work properly as expected, being interrumped or crashing for example when used to |
| 49 | + | parameter. |
| 50 | - | computed sets of permutations greater than 10 ("a" letter).
|
| 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 | - | Observation: There exists better known algorithms/methods for computing pemutations. |
| 54 | + | representing it as digit in a base greater than the decimal. The program |
| 55 | - | The present program is merely another one more among the possible implementations for |
| 55 | + | is theoretically limited up to 36 digits enumerated from zero. |
| 56 | - | doing such jobs. |
| 56 | + | |
| 57 | iv] Depending on the resources available during the execution, this program | |
| 58 | - | See for example the entry A055881 at OEIS.org, specifically the comment by Joerg Arndt. |
| 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 | - | The purpose on writing this program was to serve as ilustration for the algorithm known |
| 60 | + | letter). |
| 61 | - | as Steinhaus-Jhonson-Trotter, and additionally about how to do these thing using the |
| 61 | + | |
| 62 | - | hard disk instead the primary memory. |
| 62 | + | |
| 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 | - | my_string=string[15]; (* Mem. saving measure: Limit only 16 bytes per string. Up to the first 15! permutations only *) |
| 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 | - | insert:char; |
| 92 | + | |
| 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 | - | insert:=digit[size_i]; |
| 123 | + | |
| 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. |