Permutations: Difference between revisions
Content added Content deleted
(Added solution for EDSAC.) |
|||
Line 2,815: | Line 2,815: | ||
2341 1342 2143 1243 3124 3214 2314 |
2341 1342 2143 1243 3124 3214 2314 |
||
1324 2134 1234 |
1324 2134 1234 |
||
</pre> |
|||
=={{header|EDSAC order code}}== |
|||
Uses two subroutines which respectively |
|||
(1) Generate the first permutation in lexicographic order; |
|||
(2) Return the next permutation in lexicographic order, or set a flag to indicate there are no more permutations. |
|||
The algorithm for (2) is the same as in the Wikipedia article "Permutation". |
|||
<lang edsac> |
|||
[Permutations task for Rosetta Code.] |
|||
[EDSAC program, Initial Orders 2.] |
|||
T51K P200F [G parameter: start address of subroutines] |
|||
T47K P100F [M parameter: start address of main routine] |
|||
[====================== G parameter: Subroutines =====================] |
|||
E25K TG GK |
|||
[Constants used in the subroutines] |
|||
[0] AF [add to address to make A order for that address] |
|||
[1] SF [add to address to make S order for that address] |
|||
[2] UF [(1) add to address to make U order for that address] |
|||
[(2) subtract from S order to make T order, same address] |
|||
[3] OF [add to A order to make T order, same address] |
|||
[----------------------------------------------------------- |
|||
Subroutine to initialize an array of n short (17-bit) words |
|||
to 0, 1, 2, ..., n-1 (in the address field). |
|||
Parameters: 4F = address of array; 5F = n = length of array. |
|||
Workspace: 0F, 1F.] |
|||
[4] A3F [plant return link as usual] |
|||
T19@ |
|||
A4F [address of array] |
|||
A2@ [make U order for that address] |
|||
T1F [store U order in 1F] |
|||
A5F [load n = number of elements (in address field)] |
|||
S2F [make n-1] |
|||
[Start of loop; works backwards, n-1 to 0] |
|||
[11] UF [store array element in 0F] |
|||
A1F [make order to store element in array] |
|||
T15@ [plant that order in code] |
|||
AF [pick up element fron 0F] |
|||
[15] UF [(planted) store element in array] |
|||
S2F [dec to next element] |
|||
E11@ [loop if still >= 0] |
|||
TF [clear acc. before return] |
|||
[19] ZF [overwritten by jump back to caller] |
|||
[------------------------------------------------------------------- |
|||
Subroutine to get next permutation in lexicographic order. |
|||
Uses same 4-step algorithm as Wikipedia article "Permutations", |
|||
but notation in comments differs from that in Wikipedia. |
|||
Parameters: 4F = address of array; 5F = n = length of array. |
|||
0F is returned as 0 for success, < 0 if passed-in |
|||
permutation is the last. |
|||
Workspace: 0F, 1F.] |
|||
[20] A3F [plant return link as usual] |
|||
T103@ |
|||
[Step 1: Find the largest index k such that a{k} > a{k-1}. |
|||
If no such index exists, the passed-in permutation is the last.] |
|||
A4F [load address of a{0}] |
|||
A@ [make A order for a{0}] |
|||
U1F [store as test for end of loop] |
|||
A5F [make A order for a{n}] |
|||
U96@ [plant in code below] |
|||
S2F [make A order for a{n-1}] |
|||
T43@ [plant in code below] |
|||
A4F [load address of a{0}] |
|||
A5F [make address of a{n}] |
|||
A1@ [make S order for a{n}] |
|||
T44@ [plant in code below] |
|||
[Start of loop for comparing a{k} with a{k-1}] |
|||
[33] TF [clear acc] |
|||
A43@ [load A order for a{k}] |
|||
S2F [make A order for a{k-1}] |
|||
S1F [tested all yet?] |
|||
G102@ [if yes, jump to failed (no more permutations)] |
|||
A1F [restore accumulator after test] |
|||
T43@ [plant updated A order] |
|||
A44@ [dec address in S order] |
|||
S2F |
|||
T44@ |
|||
[43] SF [(planted) load a{k-1}] |
|||
[44] AF [(planted) subtract a{k}] |
|||
E33@ [loop back if a{k-1} > a{k}] |
|||
[Step 2: Find the largest index j >= k such that a{j} > a{k-1}. |
|||
Such an index j exists, because j = k is an instance.] |
|||
TF [clear acc] |
|||
A4F [load address of a{0}] |
|||
A5F [make address of a{n}] |
|||
A1@ [make S order for a{n}] |
|||
T1F [save as test for end of loop] |
|||
A44@ [load S order for a{k}] |
|||
T64@ [plant in code below] |
|||
A43@ [load A order for a{k-1}] |
|||
T63@ [plant in code below] |
|||
[Start of loop] |
|||
[55] TF [clear acc] |
|||
A64@ [load S order for a{j} (initially j = k)] |
|||
U75@ [plant in code below] |
|||
A2F [inc address (in effect inc j)] |
|||
S1F [test for end of array] |
|||
E66@ [jump out if so] |
|||
A1F [restore acc after test] |
|||
T64@ [update S order] |
|||
[63] AF [(planted) load a{k-1}] |
|||
[64] SF [(planted) subtract a{j}] |
|||
G55@ [loop back if a{j} still > a{k-1}] |
|||
[66] |
|||
[Step 3: Swap a{k-1} and a{j}] |
|||
TF [clear acc] |
|||
A63@ [load A order for a{k-1}] |
|||
U77@ [plant in code below, 2 places] |
|||
U94@ |
|||
A3@ [make T order for a{k-1}] |
|||
T80@ [plant in code below] |
|||
A75@ [load S order for a{j}] |
|||
S2@ [make T order for a{j}] |
|||
T78@ [plant in code below] |
|||
[75] SF [(planted) load -a{j}] |
|||
TF [park -a{j} in 0F] |
|||
[77] AF [(planted) load a{k-1}] |
|||
[78] TF [(planted) store a{j}] |
|||
SF [load a{j} by subtracting -a{j}] |
|||
[80] TF [(planted) store in a{k-1}] |
|||
[Step 4: Now a{k}, ..., a{n-1} are in decreasing order. |
|||
Change to increasing order by repeated swapping.] |
|||
[81] A96@ [counting down from a{n} (exclusive end of array)] |
|||
S2F [make A order for a{n-1}] |
|||
U96@ [plant in code] |
|||
A3@ [make T order for a{n-1}] |
|||
T99@ [plant] |
|||
A94@ [counting up from a{k-1} (exclusive)] |
|||
A2F [make A order for a{k}] |
|||
U94@ [plant] |
|||
A3@ [make T order for a{k}] |
|||
U97@ [plant] |
|||
S99@ [swapped all yet?] |
|||
E101@ [if yes, jump to exit from subroutine] |
|||
[Swapping two array elements, initially a{k} and a{n-1}] |
|||
TF [clear acc] |
|||
[94] AF [(planted) load 1st element] |
|||
TF [park in 0F] |
|||
[96] AF [(planted) load 2nd element] |
|||
[97] TF [(planted) copy to 1st element] |
|||
AF [load old 1st element] |
|||
[99] TF [(planted) copy to 2nd element] |
|||
E81@ [always loop back] |
|||
[101] TF [done, return 0 in location 0F] |
|||
[102] TF [return status to caller in 0F; also clears acc] |
|||
[103] ZF [(planted) jump back to caller] |
|||
[==================== M parameter: Main routine ==================] |
|||
[Prints all 120 permutations of the letters in 'EDSAC'.] |
|||
E25K TM GK |
|||
[Constants used in the main routine] |
|||
[0] P900F [address of permutation array] |
|||
[1] P5F [number of elements in permutation (in address field)] |
|||
[Array of letters in 'EDSAC', in alphabetical order] |
|||
[2] AF CF DF EF SF |
|||
[7] O2@ [add to index to make O order for letter in array] |
|||
[8] P12F [permutations per printed line (in address field)] |
|||
[9] AF [add to address to make A order for that address] |
|||
[Teleprinter characters] |
|||
[10] K2048F [set letters mode] |
|||
[11] !F [space] |
|||
[12] @F [carriage return] |
|||
[13] &F [line feed] |
|||
[14] K4096F [null] |
|||
[Entry point, with acc = 0.] |
|||
[15] O10@ [set teleprinter to letters] |
|||
S8@ [intialize -ve count of permutations per line] |
|||
T7F [keep count in 7F] |
|||
A@ [pass address of permutation array in 4F] |
|||
T4F |
|||
A1@ [pass number of elements in 5F] |
|||
T5F |
|||
[22] A22@ [call subroutine to initialize permutation array] |
|||
G4G |
|||
[Loop: print current permutation, then get next (if any)] |
|||
[24] A4F [address] |
|||
A9@ [make A order] |
|||
T29@ [plant in code] |
|||
S5F [initialize -ve count of array elements] |
|||
[28] T6F [keep count in 6F] |
|||
[29] AF [(planted) load permutation element] |
|||
A7@ [make order to print letter from table] |
|||
T32@ [plant in code] |
|||
[32] OF [(planted) print letter from table] |
|||
A29@ [inc address in permutation array] |
|||
A2F |
|||
T29@ |
|||
A6F [inc -ve count of array elements] |
|||
A2F |
|||
G28@ [loop till count becomes 0] |
|||
A7F [inc -ve count of perms per line] |
|||
A2F |
|||
E44@ [jump if end of line] |
|||
O11@ [else print a space] |
|||
G47@ [join common code] |
|||
[44] O12@ [print CR] |
|||
O13@ [print LF] |
|||
S8@ |
|||
[47] T7F [update -ve count of permutations in line] |
|||
[48] A48@ [call subroutine for next permutation (if any)] |
|||
G20G |
|||
AF [test 0F: got a new permutation?] |
|||
E24@ [if so, loop to print it] |
|||
O14@ [no more, output null to flush teleprinter buffer] |
|||
ZF [halt program] |
|||
E15Z [define entry point] |
|||
PF [enter with acc = 0] |
|||
[end] |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
ACDES ACDSE ACEDS ACESD ACSDE ACSED ADCES ADCSE ADECS ADESC ADSCE ADSEC |
|||
AECDS AECSD AEDCS AEDSC AESCD AESDC ASCDE ASCED ASDCE ASDEC ASECD ASEDC |
|||
CADES CADSE CAEDS CAESD CASDE CASED CDAES CDASE CDEAS CDESA CDSAE CDSEA |
|||
CEADS CEASD CEDAS CEDSA CESAD CESDA CSADE CSAED CSDAE CSDEA CSEAD CSEDA |
|||
DACES DACSE DAECS DAESC DASCE DASEC DCAES DCASE DCEAS DCESA DCSAE DCSEA |
|||
DEACS DEASC DECAS DECSA DESAC DESCA DSACE DSAEC DSCAE DSCEA DSEAC DSECA |
|||
EACDS EACSD EADCS EADSC EASCD EASDC ECADS ECASD ECDAS ECDSA ECSAD ECSDA |
|||
EDACS EDASC EDCAS EDCSA EDSAC EDSCA ESACD ESADC ESCAD ESCDA ESDAC ESDCA |
|||
SACDE SACED SADCE SADEC SAECD SAEDC SCADE SCAED SCDAE SCDEA SCEAD SCEDA |
|||
SDACE SDAEC SDCAE SDCEA SDEAC SDECA SEACD SEADC SECAD SECDA SEDAC SEDCA |
|||
</pre> |
</pre> |
||