caydist: Cayley distance

In permutations: The Symmetric Group: Permutations of a Finite Set

Cayley distance

Description

Cayley distance and associated metrics for permutations

Usage

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

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

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.

Value

Generally return non-negative integers

Note

Function ncyc(a, TRUE) returns the number of nontrivial cycles. Thus, if a is (12)(567), then ncyc(a, TRUE) returns 2. If argument discard1 is FALSE, then length-1 cycles are not discarded and ncyc(a, FALSE) returns 4 [because a is equivalent to (12)(3)(4)(567), which has 4 cycles].

The Cayley distance between two permutations a and b is defined a the least number of swaps to go from a to b. Operationally:

d_\mathrm{Cayley}(a,b) = n-c(a^{-1}b)

where c(x) is ncyc(a, FALSE). Actually it uses d_\mathrm{Cayley}(a,b) = n-c(ab^{-1}) internally, for efficiency reasons. This does not matter, for the shape of ab is the same as the shape of ba: for any permutations x,y we have \operatorname{shape}(x) = \operatorname{shape}(x^{-1}) and \operatorname{shape}(x)=\operatorname{shape}(y^{-1}xy). Then

\operatorname{shape}(ab) = \operatorname{shape}(b^{-1}a^{-1}) = \operatorname{shape}(bb^{-1}a^{-1}b^{-1}) = \operatorname{shape}(a^{-1}b^{-1}) = \operatorname{shape}(ba).

Author(s)

Robin K. S. Hankin

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

permutations documentation built on July 13, 2026, 5:07 p.m.