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. |