factoradic <- function(n) {
# Takes a number, n, and returns a Factoradic representation
# of that number. Execution time is below proportional to
# the size of n
# The factoradic representation of an integer encodes that
# integer as a series of smaller integers that, when multiplied
# by an incrementing factoridal value will reproduce the number
#
# (So c(7 5 1 1 0) = 0*(0!) + 1*(1!) + 1*(2!) + 5*(3!) + 7(4!)
#
# if some conventions are followed (that is, preferring 1! to 0!
# and never putting a number larger that it's positional coefficient
# in a particular slot) then each integer has a unique representation
# in this form.
# see http://en.wikipedia.org/wiki/Factoradic for more complete
# (and likely more accurate) information
factoradic_below <- function(integer, spot) {
if(integer < spot) { integer }
else {
nextdigit <- integer %% spot
restoftheinteger <- integer %/% spot
head <- factoradic_below(restoftheinteger, spot + 1)
c(head, nextdigit)
}
}#factoradic_below
factoradic_below(n, as.bigz(1));
}
permutationNumber <- function(len, ix) {
# Returns permutation number ix of the permutations
# of length len. Each permutation is exactly determined
# by the arguments. Execution time is proportional
# to the size of ix.
##Right now, no protection from producing more permutations than are possible.
offset_perm_ixes_longints <- factoradic(ix)
# The whole point of these numbers is they're *much* smaller
# than the "raw" index, so we're (probably) finally out of
# the woods with loss of precision
offset_perm_ixes <- as.numeric(offset_perm_ixes_longints)
perm_ixes <- offset_perm_ixes + 1
leading_one_count <- len - length(perm_ixes)
perm_ixes <- c(rep(1, leading_one_count), perm_ixes)
start_perm <- 1:len;
ret_perm <- c();
for(tail_ix in perm_ixes) {
tail <- start_perm[ tail_ix ]
ret_perm <- c(ret_perm, tail)
start_perm <- start_perm[ - tail_ix ]
}
ret_perm
}