allperms: All permutations with given characteristics

Description

Functionality to enumerate permutations given different characteristics. In the following, n is assumed to be a non-negative integer. Permutations, in general, are coerced to cycle form.

allperms(n) returns all $n!$ permutations of $[n]$ .
allcycn() returns all $(n - 1)!$ permutations of $[n]$ comprising a single cycle of length $n$ .
allcyc(s) returns all single-cycle permutations of set $s$ . If $s$ has a repeated value, an opaque error message is returned.
allpermslike(o) takes a length-one vector o of permutations and returns a vector comprising permutations with the same shape and cycle sets as it argument.
some_perms_shape(part) takes an integer partition part, as in a set of non-negative integers, and returns a vector comprising every permutation of size sum(part) with shape part that has its cycles in increasing order.
all_cyclic_shuffles(u) takes a permutation u and returns a vector comprising of all permutations with the same shape and cycle sets. It is vectorized so that argument u may be a vector of permutations.
all_perms_shape(p) takes a permutation p and returns a vector of all permutations of size sum(p) and shape p.

Usage

allperms(n)
allcycn(n)
allcyc(s)
allpermslike(o)
some_perms_shape(shape)
all_cyclic_shuffles(o)
all_perms_shape(shape)

Arguments

shape: A set of strictly positive integers, interpreted as the shape of a partition
s: A set of strictly positive integers, interpreted as a set on which permutations are defined
n: The size of the permutation
o: A vector of permutations, coerced to cycle form. Function allpermslike() considers only the first element

Author

Robin K. S. Hankin

Details

Function allperms() is very basic (the idiom is word(t(partitions::perms(n)))) but is here for completeness.

References

M. C. Er 1989 “Efficient enumeration of cyclic permutations in situ”. International Journal of Computer Mathematics, volume 29:2-4, pp121-129.

Examples

Run this code


allperms(5)

allcycn(5)

allcyc(c(5,6,8,3))

allpermslike(as.cycle("(12)(34)(5678)"))
allpermslike(rgivenshape(c(1,1,3,4)))
some_perms_shape(c(2,2,4))
all_cyclic_shuffles(cyc_len(3:5))

all_perms_shape(c(2,2,3))
all_perms_shape(c(2,2,1,1))  # size 6 (length-1 cycles vanish)

Run the code above in your browser using DataLab

The Learning Leader's Guide to AI Literacy