Permutations: Difference between revisions
Added solution for EDSAC.
(Added solution for EDSAC.) |
|||
Line 2,815:
2341 1342 2143 1243 3124 3214 2314
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>
| |||