Simplex number calculation (all dimensions) in python

Question

How can I calculate simplex numbers in all dimensions?
Example:

dimension:     2|      3|      4|
simpl(1)       1|      1|      1|
simpl(2)       3|      4|      5|
simpl(3)       6|     10|     15|
simpl(4)      10|     20|     35|
simpl(5)      15|     35|     70|

First I considered about a recursive implementation (in python):

def simplex(n, dim):
    if dim == 1:
        return n
    else:
        i = 1
        ret = 0
        while i <= n:
            ret += simplex(i, dim-1)
            i+=1
        return ret

The algorithm works, but because of the recursion its really slow, especially if your dimension number is 5 or higher.

Answer 1

You should use a for loop rather than a while loop to solve the problem. This is as you're just re-writing a for loop. Using a for loop you can change the loop to a comprehension, and take the sum of it. This allows you to get the code:

def simplex(n, dim):
    if dim == 1:
        return n
    dim -= 1
    return sum(simplex(i, dim) for i in range(1, n + 1))

However this can be simplified. When dim is the bullet point the function is:

1. \$n\$
2. \$\Sigma_{i = 1}^{n} i\$
   \$= \frac{n(n + 1)}{2}\$
3. \$\Sigma_{i = 1}^{n} (\Sigma_{j = 1}^{i} j)\$
   \$= \frac{n(n + 1)(n + 2)}{6}\$
4. \$\Sigma_{i = 1}^{n} (\Sigma_{j = 1}^{i} (\Sigma_{k = 1}^{j} k)))\$
   \$= \frac{n(n + 1)(n + 2)(n + 3)}{24}\$
5. \$\Sigma_{i = 1}^{n} (\Sigma_{j = 1}^{i} (\Sigma_{k = 1}^{j} (\Sigma_{l = 1}^{k} l))))\$
   \$= \frac{n(n + 1)(n + 2)(n + 3)(n + 4)}{120}\$

Since we're getting a pattern, we know that the top part of the fraction is:

\$\Pi_{i = 0}^{dim - 1} n + i\$

And if we use oeis to find the denominator it says it's probably the factorial sequence. And so it's likely:

\$\frac{\Pi_{i = 0}^{dim - 1} n + i}{dim!}\$

This is actually really easy to write in Python. And so you can get a significant speed up.

from functools import reduce
from math import factorial
from operator import mul

def simplex(n, dim):
    return reduce(mul, (n + i for i in range(dim))) // factorial(dim)

Answer 2

• consistency: spaces around operators (esp. +=) is not always the same, you should stick to a space before and a space after.
• conditions: since you return from your first if, you don't need the else clause. This saves an indentation level and help distinguish the general algorithm from the special case.

• iteration: you don't need a while loop with an explicit index. for loops are prefered in python.

  for i in range(1, n + 1):
      ret += simplex(i, dim - 1)
  

• additions: the sum builtin function should be faster than an explicit accumulation loop. You can combine it with a generator expression for better efficiency.

Overall, the code could be written:

def simplex(n, dim):
    if dim == 1:
        return n

    return sum(simplex(i, dim-1) for i in range(1, n+1))

---

As regard to the efficiency part, since your are computing results for the lower dimensions several times, you may want to use some form of caching. Take a look at the several techniques of memoization.

Answer 3

Fortunatly, there is a iterative variant based on a sum formula by Gauss (the Gauss formula is only for the 2nd dimension):

def fac(n):
    i = 1
    e = 1
    while i <= n:
        e*=i
        i+=1
    return e

def simplex(n, dim):
    i = 0
    ret = 1
    while i < dim:
        ret*=(n+i)
        i+=1
    ret /= fac(dim)
    return ret