mat ← ##.pmat n ⍝ Permutation matrix of ⍳⍵.
[pmat] takes an integer scalar [n] and returns a !n row matrix of the permutat-
ions of ⍳n.
Technical notes:
The method used here is to take each item of ⍳n in turn and append all sub-
permutations of the remaining (n-1) items. This produces result items in ascend-
ing order. Thus, for any ⍵: {⍵≡⍳⍴⍵}⍋pmat ⍵.
The code looks like this:
pmat←{ ⍝ Permutation matrix of ⍳⍵.
{ ⍝ perms of ⍳⍵:
1≥⍴⍵:↑,↓⍵ ⍝ short vector: done.
↑⍪/⍵,∘∇¨⍵∘~¨⍵ ⍝ items prefix sub-perms of remainder.
}⍳⍵ ⍝ permutations of identity perm.
}
Perttu Pakarinen suggests the following _much faster_ version. It produces rows
in non-ascending order but could easily be modified: {⍵[⍋⍵;]}.
prm←{
(⎕IO ⎕ML)←1 3
(×\⍳⍵){0∊⍴⍺:⍵ ⋄ (r c)←⍴⍵
(1↓⍺)∇(r/0,⍳c)⌽(⍺[1],c+1)⍴(↑⍴⍺),⍵}1 0⍴0
}
For large values of ⍵, the resulting permutation matrix takes a large amount of
workspace. In this case, it might be better to apply an auxiliary function to
each permutation as it is generated. The following operator does the trick:
perms←{ ⍝ Apply ⍺⍺ to each perm of ⍳⍵
⍬ ⍺⍺{ ⍝ null accumulator
1≥⍴⍵:⍺⍺ ⍺,⍵ ⍝ short tail: apply operand to perm
(⍺∘,¨⍵)∇¨⍵∘~¨⍵ ⍝ transfer each tail item to head
}⍳⍵ ⍝ for initial vector.
}
Roger Hui provides this even faster version:
pmat2←{{,[⍳2]↑(⊂⊂⎕io,1+⍵)⌷¨⍒¨↓∘.=⍨⍳1+1↓⍴⍵}⍣⍵⍉⍪⍬}
translated from perm2 in http://www.jsoftware.com/jwiki/Essays/Permutations
itself a translation from APL.
John Niss Hansen's "perm" functions
-----------------------------------
John provides these functions, which produce a more structured result:
⎕io←0 ⍝ Using index origin 0
perm1←{⍵=0:⍬ ⋄ ((⍳⍵)⌽⍵ ⍵⍴⍳⍵)[;0,1+∇ ⍵-1]} ⍝ Recursive indexing
]display perm1¨ ⍳4
┌→─────────────────────────┐
│ ┌⊖┐ ┌→┐ ┌┌→──┐ ┌┌┌→────┐ │
│ │0│ ↓0│ ↓↓0 1│ ↓↓↓0 1 2│ │
│ └~┘ └~┘ ││ │ │││ │ │
│ ││1 0│ │││0 2 1│ │
│ └└~──┘ │││ │ │
│ │││ │ │
│ │││1 2 0│ │
│ │││ │ │
│ │││1 0 2│ │
│ │││ │ │
│ │││ │ │
│ │││2 0 1│ │
│ │││ │ │
│ │││2 1 0│ │
│ └└└~────┘ │
└∊─────────────────────────┘
⍝ Non-recursive from natural adress-box:
permn←{i←⍳⍵ ⋄ p←(i∘~¨i),¨i ⋄ {⊃{⍵[⍺⊃p]}/⍵,⊂i}¨⍳1+i}
]display permn¨ ⍳4
┌→─────────────────────────────────────────────────────────────┐
│ ┌─────┐ ┌→────┐ ┌→────────────┐ ┌┌→────────────────────────┐ │
│ │ ┌⊖┐ │ │ ┌→┐ │ ↓ ┌→──┐ ┌→──┐ │ ↓↓ ┌→────┐ ┌→────┐ ┌→────┐ │ │
│ │ │0│ │ │ │0│ │ │ │0 1│ │1 0│ │ ││ │0 1 2│ │1 0 2│ │2 0 1│ │ │
│ │ └~┘ │ │ └~┘ │ │ └~──┘ └~──┘ │ ││ └~────┘ └~────┘ └~────┘ │ │
│ └∊────┘ └∊────┘ └∊────────────┘ ││ ┌→────┐ ┌→────┐ ┌→────┐ │ │
│ ││ │0 2 1│ │1 2 0│ │2 1 0│ │ │
│ ││ └~────┘ └~────┘ └~────┘ │ │
│ └└∊────────────────────────┘ │
└∊─────────────────────────────────────────────────────────────┘
permh←{0≡⍵:⍬ ⋄ pe←{1=≢⍵:⍵ ⋄ ↑⍵∘{⍵(pe ⍺~⍵)}¨⍵} ⋄ pe ⍳⍵} ⍝ As hierarchy
]display permh¨ ⍳4
┌→──────────────────────────────────┐
│ ┌⊖┐ ┌→┐ ┌→──────┐ ┌→────────────┐ │
│ │0│ │0│ ↓ ┌→┐ │ ↓ ┌→──────┐ │ │
│ └~┘ └~┘ │ 0 │1│ │ │ 0 ↓ ┌→┐ │ │ │
│ │ └~┘ │ │ │ 1 │2│ │ │ │
│ │ ┌→┐ │ │ │ └~┘ │ │ │
│ │ 1 │0│ │ │ │ ┌→┐ │ │ │
│ │ └~┘ │ │ │ 2 │1│ │ │ │
│ └∊──────┘ │ │ └~┘ │ │ │
│ │ └∊──────┘ │ │
│ │ ┌→──────┐ │ │
│ │ 1 ↓ ┌→┐ │ │ │
│ │ │ 0 │2│ │ │ │
│ │ │ └~┘ │ │ │
│ │ │ ┌→┐ │ │ │
│ │ │ 2 │0│ │ │ │
│ │ │ └~┘ │ │ │
│ │ └∊──────┘ │ │
│ │ ┌→──────┐ │ │
│ │ 2 ↓ ┌→┐ │ │ │
│ │ │ 0 │1│ │ │ │
│ │ │ └~┘ │ │ │
│ │ │ ┌→┐ │ │ │
│ │ │ 1 │0│ │ │ │
│ │ │ └~┘ │ │ │
│ │ └∊──────┘ │ │
│ └∊────────────┘ │
└∊──────────────────────────────────┘
Beside generating permutations, one can also decompose permutations into cycles
and also determine the sign of a permutation.
⎕IO←0 ⍝ using index origin 0
permcycles←{ ⍝ Find cycles of a permutation of the vector ⍳≢⍵
lng←≢perm←⍵
normalize←{(⍵⍳⌊/⍵)⌽⍵} ⍝ Shift cycle so smallest element first
∪normalize∘∪¨↓⍉↑{perm[⍵]}\lng/⊂perm ⍝ Scan apply the permutation lng times
⍝ and retain unique cycles
}
cyclesign←{ ⍝ Sign of permutation cycles
⊃(1 ¯1)[⊃2|+/¯1+⍴¨⍵]
}
And from here we easily get:
permsign ← cyclesign∘permcycles
For the lovers of recursion we could also write permcycles as:
permcycles←{⍝ Find cycles of a permutation of the vector ⍳≢⍵
lng←≢perm←⍵ ⍝ Local variables
res←⍬ ⍝ Initial result vector
cycles←{ ⍝ Recursive finding cycles
⍬≡⍵:⍬
res,←⊂c←∪{perm[⍵]}\lng/⊃⍵ ⍝ Follow first element through its cycle elements, append cycle to result
∇ ⍵~c ⍝ Continue with the rest
}
dumy←cycles perm ⍝ Activate the process
{(⍵⍳⌊/⍵)⌽⍵}¨res ⍝ Result as side-effect, Normalized by shift smallest element to first position
}
I will finish this with 2 more non-recursive permutation generators, that funnily
enough both produce the same reult.
First, a semi-oneliner for the rich in computer resources:
permz←{all←↓⍉(⍵/⍵)⊤⍳⍵*⍵ ⋄ ↑(∧/¨(⊂⍳⍵)∊¨all)/all} ⍝ Select ⍵-digit numbers in ⍵-radix with ⍵ different digits
Secondly, the same normal sequence done by iterative swapping of tail elements.
permn←{ ⍝ Permutations of order ⍵, ⎕io←0 ⍝ NON recursive
bas←⌽⍳⍵ ⍝ Basic vector, initialy reversed-permutated
swaps←(⊂⍳⍵){(⍵↑⍺),⌽⍵↓⍺}¨⌽⍳⍵+1 ⍝ Tail-swaps as the basic permutaions
drumbeat←⊃+/(!⍵)⍴¨(!⍳⍵)↑¨1 ⍝ The sequence of swaps
↑{##.bas←##.bas[⍵⊃swaps]}¨drumbeat ⍝ Each element calculated from previous, with a trace of bas
}
]display permz¨⍳4 ⍝ Same as permn
┌→──────────────────────┐
│ ┌⊖┐ ┌→┐ ┌→──┐ ┌→────┐ │
│ ↓0│ ↓0│ ↓0 1│ ↓0 1 2│ │
│ └─┘ └─┘ │1 0│ │0 2 1│ │
│ └───┘ │1 0 2│ │
│ │1 2 0│ │
│ │2 0 1│ │
│ │2 1 0│ │
│ └─────┘ │
└───────────────────────┘
]display ⍴¨ permz¨⍳4
┌→────────────────────────┐
│ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ │
│ │1 0│ │1 1│ │2 2│ │6 3│ │
│ └───┘ └───┘ └───┘ └───┘ │
└─────────────────────────┘
Examples:
pmat 3 ⍝ 3-perms.
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
{⍵[pmat⍴⍵]}'tic' 'tac' 'toe' ⍝ Perms of nested vector.
tic tac toe
tic toe tac
tac tic toe
tac toe tic
toe tic tac
toe tac tic
4 3 2⍴↓{⍵[pmat⍴⍵]}'abcd' ⍝ Folded perms of simple 4-vector.
abcd abdc
acbd acdb
adbc adcb
bacd badc
bcad bcda
bdac bdca
cabd cadb
cbad cbda
cdab cdba
dabc dacb
dbac dbca
dcab dcba
⍴pmat 10 ⍝ !⍵ rows.
3628800 10
display∘pmat¨2 1 0 ⍝ Limiting cases
┌→──┐ ┌→┐ ┌⊖┐
↓1 2│ ↓1│ ↓0│
│2 1│ └~┘ └~┘
└~──┘
(!0 to 5) ≡ ≢∘pmat¨0 to 5 ⍝ Result lengths.
1
⍝ Rows of the permutation matrix form
{⍵⍳⍵∘.{⍺⊃¨⊂⍵}⍵}↓pmat 3 ⍝ a group under ⊃¨∘⊂ with identity ⍳⍵.
1 2 3 4 5 6
2 1 4 3 6 5
3 5 1 6 2 4
4 6 2 5 1 3
5 3 6 1 4 2
6 4 5 2 3 1
⎕∘← perms 3 ⍝ show each permutation.
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
See also: cmat
Back to: contents
Back to: Workspaces