# 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.