Vocabulary/acapdot
>> << Back to: Vocabulary Thru to: Dictionary
A. y Anagram Index
Rank 1 -- operates on lists of y, producing an atom for each one -- WHY IS THIS IMPORTANT?
A. y converts the permutation y into its permutation number (also called its anagram index).
A. 3 1 2 0 21
A list of length n is a permutation if it contains each of the atoms of i.n .
N=: 4 NB. Confine attention to permutations on 4 points
A=: 'ABCD' NB. N points provided for a given permutation to act on
p=: 2 0 1 3 NB. a given permutation on N points
] i=: i.N NB. the identity permutation on N points
0 1 2 3
p { A NB. Permute 'ABCD' by permutation: p
CABD
A. p NB. The AI of permutation: p
12
A. i NB. The AI of permutation: i (identity)
0
Common uses
1. Work conveniently with permutations, using the permutation number instead of the permutation itself.
2. Explore the subgroups of a given permutation group.
Example: the symmetric group of all permutations on 4 points, known as Sym(4) or S4.
Representing each permutation by its AI, we can represent the set S4 in J as follows:
N=: 4 ] S4=: i. !N NB. a list of AIs 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
plus a group product operation: mul, between any two AIs (the elements of S4)
a2p=: 3 : 'y A. i.N' NB. AI --> permutation
mul=: 4 : 'A. (a2p x) { (a2p y)'"0 NB. (AI) mul (AI) --> (AI)
mul always yields another AI, viz an element in S4.
The set of all permutations on N points forms a mathematical group under the operation: mul. That is:
- the set is closed under mul
z=: S4 mul/ S4 ~. ,z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
- The operation is associative, i.e. expressions in mul can be bracketed in any order
] 'a b c'=: 3 ? #S4 3 2 17 assert (a mul (b mul c)) -: ((a mul b) mul c)
- There exists a unique identity element. In S4 this is 0.
- Every AI a has a unique right inverse r and a unique left inverse 's', such that
assert i -: (a mul r) assert i -: (s mul a)
3. Build the Cayley Table of the subgroup of S4 generated by the AI: 9 under mul
9 mul 9 16 9 mul 9 mul 9 18 9 mul 9 mul 9 mul 9 0 S=: 0 9 16 18 NB. Define candidate set S
Does S form a group under mul? If so then (S mul/ S) will contain only items of S
S mul/ S NB. the Cayley Table of subgroup S 0 9 16 18 9 16 18 0 16 18 0 9 18 0 9 16
More Information
1. The permutation y can be expressed in either cycle or direct form.
2. The permutation number of a permutation is the index of the direct form of the permutation in the table whose rows are all the direct permutations of the same length.
The permutation number is also called the anagram index.
a. Permutation number 0 is always the identity permutation
a. Permutation 1 always interchanges the last two elements
3. Because permutation numbers can get big, the result of A. y is an extended integer.
Details
1. A. y can be modeled as
ai =: (>:@i.@-@x:@# #. (+/@:< {.)\.) @: (C.^:(1 = L.))
x A. y Anagram
Rank 0 _ -- operates on atoms of x, and the entirety of y -- WHY IS THIS IMPORTANT?
x A. y reorders the items of y by applying the permutation of length #y whose permutation number is x.
A permutation of the letters of a word is called an anagram.
A. 2 3 1 0 NB. Calculate permutation number of a permutation
17
17 A. 'abcd' NB. Use it to permute abcd
cdba
2 3 1 0 { 'abcd' NB. This is what a permutation does
cdba
Common uses
1. Applying x to i.N gives the permutation of length N with anagram index (AI) x.
N =: 6 NB. length of permutation 26 A. i. N NB. What is permutation having AI of 26? 0 2 1 4 3 5 A. 0 2 1 4 3 5 NB. permutation --> AI 26
2. Generate all the distinct permutations of 4 items
n=: !N=: 4 NB. number of distinct permutations on N=4 points (i.n) A. i. N NB. the permutations corresponding to the list of AI's: (i.n) 0 1 2 3 0 1 3 2 0 2 1 3 0 2 3 1 0 3 1 2 0 3 2 1 1 0 2 3 1 0 3 2 1 2 0 3 1 2 3 0 1 3 0 2 1 3 2 0 2 0 1 3 2 0 3 1 2 1 0 3 2 1 3 0 2 3 0 1 2 3 1 0 3 0 1 2 3 0 2 1 3 1 0 2 3 1 2 0 3 2 0 1 3 2 1 0
3. Build a table of the anagram indexes of S4 (the symmetric group on 4 points) with their corresponding direct permutations
S4 NB. The AI's contained in S4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 $ t=: S4 A. i NB. list of corresponding permutations 24 4 (,.S4) ; t +--+-------+ | 0|0 1 2 3| | 1|0 1 3 2| | 2|0 2 1 3| | 3|0 2 3 1| | 4|0 3 1 2| | 5|0 3 2 1| | 6|1 0 2 3| | 7|1 0 3 2| | 8|1 2 0 3| | 9|1 2 3 0| |10|1 3 0 2| |11|1 3 2 0| |12|2 0 1 3| |13|2 0 3 1| |14|2 1 0 3| |15|2 1 3 0| |16|2 3 0 1| |17|2 3 1 0| |18|3 0 1 2| |19|3 0 2 1| |20|3 1 0 2| |21|3 1 2 0| |22|3 2 0 1| |23|3 2 1 0| +--+-------+
Details
1. x A. i. y can be modeled as (though improvable)
del1=: ] ({.~ , [ }.~ >:@]) i.~
aiD =: (2 {:: ((0}.@{:: ]) ; 1&{:: ((del1~ {:); ]) 2&{:: , 1&{:: {~ 0 {.@{:: ])^:(0 < 0 #@{:: ])(^:_)@:(i.@0: (, <)~ i.@[ ;~ >:@i.@-@x:@[ #. inv ]))
3 4 2 1 0 -: 5 aiD 95