Task

Write a program that generates all   permutations   of   n   different objects.   (Practically numerals!)



Related tasks
 
   Find the missing permutation
   Permutations/Derangements



 The number of samples of size k from n objects.


With   combinations and permutations   generation tasks. 






 Order Unimportant

 Order Important


 Without replacement








(


n
k


)




=

n



C

k


=



n
(
n
−
1
)
…
(
n
−
k
+
1
)


k
(
k
−
1
)
…
1





{\displaystyle {\binom {n}{k}}=^{n}\operatorname {C} _{k}={\frac {n(n-1)\ldots (n-k+1)}{k(k-1)\dots 1}}}










n



P

k


=
n
⋅
(
n
−
1
)
⋅
(
n
−
2
)
⋯
(
n
−
k
+
1
)


{\displaystyle ^{n}\operatorname {P} _{k}=n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)}




Task: Combinations

Task: Permutations


 With replacement








(



n
+
k
−
1

k


)




=

n
+
k
−
1



C

k


=



(
n
+
k
−
1
)
!


(
n
−
1
)
!
k
!





{\displaystyle {\binom {n+k-1}{k}}=^{n+k-1}\operatorname {C} _{k}={(n+k-1)! \over (n-1)!k!}}








n

k




{\displaystyle n^{k}}




Task: Combinations with repetitions

Task: Permutations with repetitions



 
[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]
 