Brandon Anzaldi - 2 years ago 118
Javascript Question

# Why is my subfactorial function off by one?

I'm working on implementing a subfactorial function in JavaScript to calculate the total number of derangements possible for

n
elements, and I seem to have screwed something up. My calculation always seems to be one high, or one low. What did I screw up? Is it a rounding error?

function subfactorial (x) {
x = parseInt(x);
var i;
var sub = 0;
var sum = 0;
sum += factorial(x);
for (i = 0; i < x; i++) {
sub += (Math.pow(-1, i)/factorial(i));
}
return sum * sub;
}

function factorial (y) {
var negative = y < 0;
y = parseInt(Math.abs(y)); // Ints only
var acc = 1;
for (y; y > 0; y--) {
acc *= y;
}
return negative ? -acc : acc;
}

function getSubfactorial () {
var val = document.getElementById('subfac').value;
document.getElementById('result').innerHTML = subfactorial(val);
}

<label for="subfac">Subfactorial input:</label>
<input type="number" id="subfac">
<button type="button" onClick="getSubfactorial()">Get Subfactorial</button>
<div id="result"></div>

For example,
subfactorial(3)
returns 3, when the answer should be 2.
subfactorial(4)
returns 8, when the answer should be 9.
subfactorial(5)
returns 45 (with a floating point rounding error) when the answer should be 44, and so on, and so forth. It seems to alternate being too low and too high between even and odd numbers respectively.

The formula I'm using comes out to be this:

In TeX:

!x = x! \sum_{k=0}^{x}\frac {(-1)^k}{k!}

Rendered TeX:

You're going to laugh:

for (i = 0; i < x; i++) {


That not what the Sum symbol means. It should be

for (i = 0; i <= x; i++) {


Also, that is the most literal-minded way to implement subfactorial imaginable. The exponentiation is just a way to represent "oscillate between positive and negative one" -- but in Javascript, there are about 10 better ways to do that. And there is no reason to use (or worry about) floating-point. Instead of calculating 1/k! and then multiplying by x!, calculate x!/k!, which can be done as

var factDiv = function(x, k) {
return (k >= x) ? 1 : (x * factDiv(x-1,k));
}

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download