permutations (version 1.1-9-1)

caydist: Cayley distance

Description

Cayley distance and associated metrics for permutations

Usage

nmoved(a)
nfixed(a)
ncyc(a, discard1 = TRUE)
caydist(a, b = id)

Value

Generally return non-negative integers

Arguments

a, b

Permutations, coerced to cycle form

discard1

Boolean, with default TRUE meaning to discard length-1 cycles and return the number of cycles with length \(>1\)

Author

Robin K. S. Hankin

Details

These functions support caydist().

Given a permutation a, nfixed(a) returns the number of elements mapped to themselves and nmoved(a) returns the number of elements moved [that is, elements not mapped to themselves]; ncyc(a) returns the number of cycles, and caydist() returns the minimum number of transpositions needed to convert a to b.

See Also

tidy

Examples

x <- rperm()
x

nmoved(x)
nfixed(x)
ncyc(x, discard1 = TRUE)
ncyc(x, discard1 = FALSE)

y <- rperm()

caydist(x,y)
all(caydist(x, y) == caydist(y, x))

z <- rperm()
all(caydist(x, z) <= caydist(x, y) + caydist(y, z))

mean(caydist(rperm(100,100)))  # compare 100 - log(100) - gamma ~= 94.82