invertPerm: Utilities for Permutation Vectors

Description

invertPerm and signPerm compute the inverse and sign of a length-n permutation vector. isPerm tests if a length-n integer vector is a valid permutation vector. asPerm coerces a length-m transposition vector to a length-n permutation vector, where m <= n.

Usage

invertPerm(p, off = 1L, ioff = 1L)
signPerm(p, off = 1L)
isPerm(p, off = 1L)
asPerm(pivot, off = 1L, ioff = 1L, n = length(pivot))
invPerm(p, zero.p = FALSE, zero.res = FALSE)

Value

By default, i.e., with off=1 and ioff=1:

invertPerm(p) returns an integer vector of length

length(p) such that p[invertPerm(p)]

and invertPerm(p)[p] are both seq_along(p), i.e., the identity permutation.

signPerm(p) returns 1 if p is an even permutation and -1 otherwise (i.e., if p is odd).

isPerm(p) returns TRUE if p is a permutation of seq_along(p) and FALSE otherwise.

asPerm(pivot) returns the result of transposing elements

i and pivot[i] of a permutation vector initialized as seq_len(n), for i in seq_along(pivot).

Arguments

p: an integer vector of length n.
pivot: an integer vector of length m.
off: an integer offset, indicating that p is a permutation of off+0:(n-1) or that pivot contains m values sampled with replacement from off+0:(n-1).
ioff: an integer offset, indicating that the result should be a permutation of ioff+0:(n-1).
n: a integer greater than or equal to m, indicating the length of the result. Transpositions are applied to a permutation vector vector initialized as seq_len(n).
zero.p: a logical. Equivalent to off=0 if TRUE and off=1 if FALSE.
zero.res: a logical. Equivalent to ioff=0 if TRUE and ioff=1 if FALSE.

Details

invertPerm(p, off, ioff=1) is equivalent to order(p) or sort.list(p) for all values of off. For the default value off=1, it returns the value of p after p[p] <- seq_along(p).

invPerm is a simple wrapper around invertPerm, retained for backwards compatibility.

Examples

Run this code

p <- sample(10L) # a random permutation vector
ip <- invertPerm(p)
s <- signPerm(p)

## 'p' and 'ip' are indeed inverses:
stopifnot(exprs = {
    isPerm(p)
    isPerm(ip)
    identical(s, 1L) || identical(s, -1L)
    identical(s, signPerm(ip))
    identical(p[ip], 1:10)
    identical(ip[p], 1:10)
    identical(invertPerm(ip), p)
})

## Product of transpositions (1 2)(2 1)(4 3)(6 8)(10 1) = (3 4)(6 8)(1 10)
pivot <- c(2L, 1L, 3L, 3L, 5L, 8L, 7L, 8L, 9L, 1L)
q <- asPerm(pivot)
stopifnot(exprs = {
    identical(q, c(10L, 2L, 4L, 3L, 5L, 8L, 7L, 6L, 9L, 1L))
    identical(q[q], seq_len(10L)) # because the permutation is odd:
    signPerm(q) == -1L
})

invPerm # a less general version of 'invertPerm'
# \dontshow{
stopifnot(exprs = {
    identical(isPerm(0L), FALSE)
    identical(signPerm(1:2),  1L)
    identical(signPerm(2:1), -1L)
    identical(invertPerm(c(3, 1:2)), c(2:3, 1L)) # 'p' of type "double",
    tryCatch(invPerm(NA), error = function(e) TRUE) # was a segfault
})
# }