Essays/Permutations

Generate the sorted table of all permutations of i.n .

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

Contributed by Roger Hui, with additional contributions by Oleg Kobchenko.