permutation misses.R

n = 7    # Number of elements to permute
k = 1E5  # Number of permutations allowed by RNG

# Declare a character vector to store permutations
permutations = character(k)
for(i in 1:k){
  # save k permutations as strings
  permutations[i] = paste(sample.int(n), collapse = "-")
}

# Number of times each permutation appeared
tallies = table(permutations)
expected = dpois(0:k, k/factorial(n))


# If some permutations haven't been picked, pad the tallies vector with zeros
# until it's length is factorial(n)
if(length(tallies) < factorial(n)){
  tallies = c(tallies, rep(0, factorial(n) - length(tallies)))
}

factorial(n) == length(tallies)

plot(table(tallies), yaxs = "i", ylim = c(0, max(table(tallies)) * 1.04))
points(0:k, min(k, factorial(n)) * expected, pch = 4, col = 2)

# Number of misses observed
sum(tallies == 0)

# Number of misses expected under Poisson model 
dpois(0, lambda = k/factorial(n)) * factorial(n)  # Using full distribution
exp(-k/factorial(n)) * factorial(n)               # Using simplified formula


p = exp(-k/factorial(n))   # Probability of missing a given permutation
1 - (1-p)^factorial(n)     # Probability of *at least one miss*