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

Incomplete permutations are made complete before the anagram index is calculated.

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=: {{y A. i.N}} NB. AI --> permutation mul=: {{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.^:(2 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 ])) 5 aiD 95 3 4 2 1 0 95 A. i.5 3 4 2 1 0