4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Good point, but I actually knew the iterative solution already at the time of asking the question (I just asked to share this in the community). As you can see, I answered the question too. I have two mentions to you: do you need the double Slash before factorial(dim)? and I like the while loop more than the for loop, because I expierienced weird things with the order of execution in for loops \$\endgroup\$ – Aemyl Sep 30 '16 at 5:41
  • \$\begingroup\$ @Aemyl I didn't see your answer when I started and finished mine, but it was a thought provoking question, :). To answer your 'mentions', (1) You need either // or /, I chose // as it matches the functions range. (2) I don't know how I can help you like for loops, but I will not retract my encouragement for you to use them. As they objectively make the function much cleaner than the equivalent using a while. \$\endgroup\$ – Peilonrayz Sep 30 '16 at 8:28
  • \$\begingroup\$ I didn't want you to retract your aspect of using for loops :) I just wanted to explain why I use while loops. \$\endgroup\$ – Aemyl Sep 30 '16 at 16:55
2
\$\begingroup\$
  • 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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ though for loops are prefered in python, I like while loops more then them, because in my opinion (and in python's) explicit is better than implicit. Another point is, I expierienced some really weird things with for loops (the order of iterating through list for example) \$\endgroup\$ – Aemyl Sep 30 '16 at 5:51
  • \$\begingroup\$ @Aemyl Out of "use <name> as a variable to iterate over <stuff> and do …" and "check this <condition> before you do … over and over again"; I don't think the latter is more explicit when, well, iterating over some stuff. And I don't know what you are trying to do with your lists, but order of iteration is always consistent in a for loop. I’d understand if you said set or dict, but not list. \$\endgroup\$ – 301_Moved_Permanently Sep 30 '16 at 7:58
  • \$\begingroup\$ sorry, I guess it was on dictionaries \$\endgroup\$ – Aemyl Sep 30 '16 at 16:53
  • \$\begingroup\$ @Aemyl Then the arbitrary ordering is built into the language. If you want to be able to control it, you may want to have a look at collections.OrderedDict. \$\endgroup\$ – 301_Moved_Permanently Oct 1 '16 at 6:24
0
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.