09-07-2018, 06:42 AM
As part of a challenge posted to r/dailyprogrammer a couple of days ago, I derived an algorithm for the subfactorial, which is similar in definition to the factorial. The subfactorial of n (!n) is the number of permutations of an ordered collection of n unique values such that no value retains its original position (these special permutations are called derangements). Intuitively, we can say that !n is always less than n! since there will always be exclusions, hence the name "subfactorial".
We can define some base cases:
subf(0) = 1 (we say that "all" of the elements in an empty collection are out of place, so we count the empty collection itself once).
subf(1) = 0 (a collection of length 1 can not be permutated, and therefore has no derangements).
And we can also derive a recursive definition. Let's say for a subfactorial of n, we append element n onto a collection of n-1 values. Element n is currently in-place, and so we must swap it with any of the other n-1 values which will then guarantee that both values are not in their original place. We can either ensure that all n-1 values are out of place (subf(n-1) cases) and swap with any of them (n-1 cases), making a term of (n-1) * subf(n-1), or we can ensure n-2 of the n-1 values are out of place (subf(n-2) cases), leaving one in-place that we swap with the new value to make out-of-place (n-1 cases), creating a second term of (n-1) * subf(n-2).
With some factoring, we get the following recursive definition:
subf(n) = (n - 1) * (subf(n - 1) + subf(n - 2))
Note how similar it is to Fibonacci, with the main difference being the multiplication at every level of recursion. Like Fibonacci, the complexity of this definition is 2^n, but it can easily be simplified into a linear, sequential algorithm where we compute starting at the base cases, going bottom-up instead of top-down.
Some more simple examples:
subf(2) = 1 (for an ordered collection [1, 2], the one valid derangement is [2, 1])
subf(3) = 2 (for an ordered collection [1, 2, 3], the valid derangemnets are [3, 1, 2] and [2, 3, 1]).
Because of its similarity to the Fibonacci algorithms, I think this may be suitable as a benchmark program in some cases, especially where hardware multiplication may be implemented. It should be noted that the subfactorial approximates the factorial function, meaning it grows faster than exponential rate (which is used to approximate Fibonacci). By !6 we reach 265, which is out of the 8-bit range, and even more quickly, !9 surpasses the size of a 16-bit integer. Regardless, I found it very interesting and potentially useful in some case.
We can define some base cases:
subf(0) = 1 (we say that "all" of the elements in an empty collection are out of place, so we count the empty collection itself once).
subf(1) = 0 (a collection of length 1 can not be permutated, and therefore has no derangements).
And we can also derive a recursive definition. Let's say for a subfactorial of n, we append element n onto a collection of n-1 values. Element n is currently in-place, and so we must swap it with any of the other n-1 values which will then guarantee that both values are not in their original place. We can either ensure that all n-1 values are out of place (subf(n-1) cases) and swap with any of them (n-1 cases), making a term of (n-1) * subf(n-1), or we can ensure n-2 of the n-1 values are out of place (subf(n-2) cases), leaving one in-place that we swap with the new value to make out-of-place (n-1 cases), creating a second term of (n-1) * subf(n-2).
With some factoring, we get the following recursive definition:
subf(n) = (n - 1) * (subf(n - 1) + subf(n - 2))
Note how similar it is to Fibonacci, with the main difference being the multiplication at every level of recursion. Like Fibonacci, the complexity of this definition is 2^n, but it can easily be simplified into a linear, sequential algorithm where we compute starting at the base cases, going bottom-up instead of top-down.
Some more simple examples:
subf(2) = 1 (for an ordered collection [1, 2], the one valid derangement is [2, 1])
subf(3) = 2 (for an ordered collection [1, 2, 3], the valid derangemnets are [3, 1, 2] and [2, 3, 1]).
Because of its similarity to the Fibonacci algorithms, I think this may be suitable as a benchmark program in some cases, especially where hardware multiplication may be implemented. It should be noted that the subfactorial approximates the factorial function, meaning it grows faster than exponential rate (which is used to approximate Fibonacci). By !6 we reach 265, which is out of the 8-bit range, and even more quickly, !9 surpasses the size of a 16-bit integer. Regardless, I found it very interesting and potentially useful in some case.
I'M BAAAAAAACK!