PPER: Partial Permutations | Ben Cunningham

PPER: Partial Permutations

Problem by Rosalind · on December 4, 2012

A partial permutation is an ordering of only objects taken from a collection containing objects (i.e., ). For example, one partial permutation of three of the first eight positive integers is given by .

The statistic counts the total number of partial permutations of objects that can be formed from a collection of objects. Note that is just the number of permutations of objects, which we found to be equal to in “Enumerating Gene Orders”.

Given: Positive integers and such that and .

Return: The total number of partial permutations , modulo 1,000,000.

Sample Dataset

21 7

Sample Output




f <- "pper.txt"

x <-
  readLines(f) %>%
  strsplit(split = " ") %>%
  unlist() %>%

n <- x[1]
k <- x[2]

cat((prod(1:n) / prod(1:(n - k))) %% 1E6)