Essays/Permutations
Generate the sorted table of all permutations of i.n .
Contents
The Dyad A.
perm=: i.@! A. i. perm 3 0 1 2 0 2 1 1 0 2 1 2 0 2 0 1 2 1 0
Inside A.
The i.@! A. i. solution begs the question of how A. does it. The question is answered in the Permutation Index page:
Each number in i.!n has a unique representation in the number system with n-i.n as bases, called the reduced representation. A. converts between a permutation index and its reduced representation, and between the reduced and the direct representations of a permutation.
base =: (-i.)@# dfr =: /:@/:@,/"1 NB. direct from reduced adot2=: dfr @ (base@] #: [) perm1=: i.@! adot2 i. perm1 3 0 1 2 0 2 1 1 0 2 1 2 0 2 0 1 2 1 0
Repeated Indexing
If p=:perm n are all the permutations of i.n and m=: \:"1 =i.n+1 are the downgrades of each row of the identity matrix of order n+1 , then ,/(0,.1+p){"2 1 m are all the permutations of order n+1 . We demonstrate this for n=:3 .
p=: perm 3 ] m=: \:"1 = i.4 0 1 2 3 1 0 2 3 2 0 1 3 3 0 1 2 <"2 (0,.1+p) {"2 1 m ┌───────┬───────┬───────┬───────┐ │0 1 2 3│1 0 2 3│2 0 1 3│3 0 1 2│ │0 1 3 2│1 0 3 2│2 0 3 1│3 0 2 1│ │0 2 1 3│1 2 0 3│2 1 0 3│3 1 0 2│ │0 2 3 1│1 2 3 0│2 1 3 0│3 1 2 0│ │0 3 1 2│1 3 0 2│2 3 0 1│3 2 0 1│ │0 3 2 1│1 3 2 0│2 3 1 0│3 2 1 0│ └───────┴───────┴───────┴───────┘ (perm 4) -: ,/ (0,.1+p){"2 1 m 1
This alternative computation of the table of all permutations is embodied in the following verb:
perm2=: 3 : 0 z=. i.1 0 for. i.y do. z=. ,/ (0,.1+z) {"2 1 \:"1 = i. 1+{:$z end. )
Column by Column
If t is the */n-i.c by c table of c selections from i.n without replacement, then the table of c+1 selections can be formed by appending to each row of t each integer i.n , and then discarding those rows having non-unique elements.
This technique is not as efficient as the repeated indexing method above. However, it is useful in situations where the permutations must meet additional requirements, and it is grossly inefficient or impossible to generate all the permutations first before discarding those that do not meet the requirements. See the N Queens Problem, Joy of n, Div9, or DivN puzzles.
col =: (*./@~:"1 # ]) @ (,/@:(,"1 0"1)) perm3=: 3 : 'col&(i.y)^:y i.1 0' col&(i.4)&.>^:(i.5) <i.1 0 ┌┬─┬───┬─────┬───────┐ ││0│0 1│0 1 2│0 1 2 3│ ││1│0 2│0 1 3│0 1 3 2│ ││2│0 3│0 2 1│0 2 1 3│ ││3│1 0│0 2 3│0 2 3 1│ ││ │1 2│0 3 1│0 3 1 2│ ││ │1 3│0 3 2│0 3 2 1│ ││ │2 0│1 0 2│1 0 2 3│ ││ │2 1│1 0 3│1 0 3 2│ ││ │2 3│1 2 0│1 2 0 3│ ││ │3 0│1 2 3│1 2 3 0│ ││ │3 1│1 3 0│1 3 0 2│ ││ │3 2│1 3 2│1 3 2 0│ ││ │ │2 0 1│2 0 1 3│ ││ │ │2 0 3│2 0 3 1│ ││ │ │2 1 0│2 1 0 3│ ││ │ │2 1 3│2 1 3 0│ ││ │ │2 3 0│2 3 0 1│ ││ │ │2 3 1│2 3 1 0│ ││ │ │3 0 1│3 0 1 2│ ││ │ │3 0 2│3 0 2 1│ ││ │ │3 1 0│3 1 0 2│ ││ │ │3 1 2│3 1 2 0│ ││ │ │3 2 0│3 2 0 1│ ││ │ │3 2 1│3 2 1 0│ └┴─┴───┴─────┴───────┘
Permutation Groups
As described in Symmetric Array, the two permutations 0&C. (rotating by 1) and _2&C. (transposing the last two items) generate the entire permutation group. Therefore, for 1<n ,
stdarg =: i.@{:@$ , ,:^:(1: -: #@$) pvp =: ~. @ (,/) @ ({"1/~) subgroup=: pvp^:_ @ stdarg perm4 =: /:~ @ subgroup @ ((,.0 _2)&C.) @ i.
<!> Note: This method takes time and space of order *:n*!n and is not practical for n>5 .
Random
The phrase n?m$n generates m random permutations of order n . It is therefore possible to generate all permutations by accumulating randomly-generated permutations until the number of unique ones so accumulated is !n .
perm5=: 3 : 0 m=. !n=. y z=. i.0,n while. m>#z do. z=. ~. z, n?m$n end. /:~ z ) accum =: [: ~. [ , (? ! $ ])@{:@$ perm5a=: /:~ @ (accum^:_) @ i. @ (0&,)
Base Representation
The permutations can be produced by appropriate selection from the base n$n representations of the integers i.n^n . However, the method requires space (and time) exponential in the size of the result.
perm6=: 3 : '(i.y) (*./"1@:(e."1) # ]) ($~ y) #: i.^~y'
Generational
The Base Representation method is built similar to comb1 in that we start with the natural sequence, convert to a base representation (binary for combinations and equal to size for permutations), and apply a filter (count of 1's for combinations and nub for permutations).
These are not practical ways of getting the result; however, they provide insight about the structure of the set in its relation to the natural sequence, which is further supported by the spectrum illustration. Thus:
We immediately see how they correspond: whereas the natural sequence repeats all items as children in the next generation, permutations skip ancestors. Thus we arrive at the following new variant:
perm7=: 3 : '(i.y) (] ,/@:(,"1 0) -."1)^:y i.1 0'
Benchmarks
Time-space numbers for each method:
The Dyad A. perm 7 0.00830189 574784 Inside A. perm1 7 0.107852 558848 Repeated Indexing perm2 7 0.0028864 660800 Column by Column perm3 7 0.273716 2230784 Permutation Groups perm4 7 -- -- Random perm5 7 0.317502 2001024 Base Representation perm6 7 1.60794 47189888 Generational perm7 7 0.0297596 692096
See also
- Permutations
- Inverse Permutation
- Permutation Index
- Self-Upgrading Permutations
- Self-Downgrading Permutations
- Symmetric Array
- Symmetries of the Square
- Cayley's Theorem
- N Queens Problem
Contributed by Roger Hui, with additional contributions by Oleg Kobchenko.