Subfactorials — Another twist on Factorials
/r/dailyprogrammer challenge 367
Original problem submitted by /u/jnazario to /r/dailyprogrammer
Almost every programmer is familiar with the factorial (n!) of a number, which is, of course, the product of the series from n to 1. An interesting aspect of the factorial operations is that it is also the number of permutations of a set of n objects.
Let’s look at the subfactorial, which is defined as the derangement of a set of n objects, or a permutation of the elements of a set such that no element will appear in its original position. We’re going to denote it as !n, but note that there is no standard notation agreed upon for the subfactorial function.
Some basic definitions:
!1 -> 0 because you always have {1}, meaning 1 is always in it’s position.
!2 -> 1 because you have {2,1}.
!3 -> 2 because you have {2,3,1} and {3,1,2}.
And so forth.
One equation for solving for subfactorials is
!n = n! / e
The challenge? Write a subfactorial program. Given an input n, we need to calculate the correct value for n. Assuming we’re given inputs as one integer per line as the original problem states, the…
