Ops.permutation {permutations}

Arithmetic Ops Group Methods for permutations

Description

Allows arithmetic operators to be used for manipulation of permutation objects such as addition, multiplication, division, integer powers, etc.

Usage

## S3 method for class 'permutation'
Ops(e1, e2)
cycle_power(x,pow)
cycle_power_single(x,pow)
cycle_sum(e1,e2)
cycle_sum_single(c1,c2)
word_equal(e1,e2)
word_prod(e1,e2)
word_prod_single(e1,e2)
permprod(x)
vps(vec,pow)
ccps(n,pow)
helper(e1,e2)
cycle_plus_integer_elementwise(x,y)
conjugation(e1,e2)

Arguments

x, e1, e2

Objects of class “permutation”

c1, c2

Objects of class cycle

pow

Integer vector of powers

vec

In function vps(), a vector of integers corresponding to a cycle

n

In function ccps(), the integer power to which cycle(seq_len(n)) is to be raised; may be positive or negative

y

In experimental function cycle_plus_integer_elementwise(), an integer

Details

Function Ops.permutation() passes binary arithmetic operators (“+”, “*”, “/”, “^”, and “==”) to the appropriate specialist function.

Multiplication, as in a*b, is effectively word_prod(a,b); it coerces its arguments to word form (because a*b = b[a]).

Raising permutations to integer powers, as in a^n, is cycle_power(a,n); it coerces a to cycle form and returns a cycle (even if n=1). Negative and zero values of n operate as expected. Function cycle_power() is vectorized; it calls cycle_power_single(), which is not. This calls vps() (“Vector Power Single”), which checks for simple cases such as pow=0 or the identity permutation; and function vps() calls function ccps() which performs the actual number-theoretic manipulation to raise a cycle to a power.

Group-theoretic conjugation is implemented: in package idiom, a^b gives inverse(b)*a*b. The notation is motivated by the identities x^(yz)=(x^y)^z and (xy)^z=x^z*y^z [or x^{yz}=(x^y)^z and (xy)^z=x^zy^z]. Internally, conjugation() is called. The concept of conjugate permutations [that is, permutations with the same shape()] is discussed at conjugate.

The sum of two permutations a and b, as in a+b, is defined if the cycle representations of the addends are disjoint. The sum is defined as the permutation given by juxtaposing the cycles of a with those of b. Note that this operation is commutative. If a and b do not have disjoint cycle representations, an error is returned. This is useful if you want to guarantee that two permutations commute (NB: permutation a commutes with a^i for i any integer, and in particular a commutes with itself. But a+a returns an error: the operation checks for disjointness, not commutativity).

Permutation “division”, as in a/b, is a*inverse(b). Note that a/b*c is evaluated left to right so is equivalent to a*inverse(b)*c. See note.

Function helper() sorts out recycling for binary functions, the behaviour of which is inherited from cbind(), which also handles the names of the returned permutation.

Experimental functionality is provided to define the “sum” of a permutation and an integer. If x is a permutation in cycle form with x=(abc), say, and n an integer, then x+n=(a+n,b+n,c+n): each element of each cycle of x is increased by n. Note that this has associativity consequences. For example, x+(x+n) might be defined but not (x+x)+n, as the two “+” operators have different interpretations. Distributivity is similarly broken (see the examples). Package idiom includes x-n [defined as x + (-n)] and n+x but not n-x as inverses are defined multiplicatively. The implementation is vectorised.

Value

None of these functions are really intended for the end user: use the ops as shown in the examples section.

Note

The class of the returned object is the appropriate one.

Unary operators to invert a permutation are problematic in the package. I do not like using “id/x” to represent a permutation inverse: the idiom introduces an utterly redundant object (“id”), and forces the use of a binary operator where a unary operator is needed. Similar comments apply to “x^-1”, which again introduces a redundant object (-1) and uses a binary operator.

Currently, “-x” returns the multiplicative inverse of x, but this is not entirely satisfactory either, as it uses additive notation: the rest of the package uses multiplicative notation. Thus x*-x == id, which looks a little odd but OTOH noone has a problem with x^-1 for inverses.

I would like to follow APL and use “/x”, but this does not seem to be possible in R. The natural unary operator would be the exclamation mark “!x”. However, redefining the exclamation mark to give permutation inverses, while possible, is not desirable because its precedence is too low. One would like !x*y to return inverse(x)*y but instead standard precedence rules means that it returns inverse(x*y). Earlier versions of the package interpreted !x as inverse(x), but it was a disaster: to implement the commutator [x,y]=x^{-1}y^{-1}xy, for example, one would like to use !x*!y*x*y, but this is interpreted as !(x*(!y*(x*y))); one has to use (!x)*(!y)*x*y. I found myself having to use heaps of brackets everywhere. This caused such severe cognitive dissonance that I removed exclamation mark for inverses from the package. I might reinstate it in the future. There does not appear to be a way to define a new unary operator due to the construction of the parser.

Author(s)

Robin K. S. Hankin

Examples

x <- rperm(10,9) # word form
y <- rperm(10,9) # word form

x*y  # products are given in word form but the print method coerces to cycle form
print_word(x*y)

x^5  # powers are given in cycle form

x^as.cycle(1:5)  # conjugation (not integer power!); coerced to word.

x*inverse(x) == id  # all TRUE


# the 'sum' of two permutations is defined if their cycles are disjoint:
as.cycle(1:4) + as.cycle(7:9)

data(megaminx)
megaminx[1] + megaminx[7:12] 

rperm() + 100

z <- cyc_len(4)
z
z+100
z + 0:5
(z + 0:5)*z

w <- cyc_len(7) + 1
(w+1)*(w-1)