#9941: faster multinomial_coefficients
--------------------------------+-------------------------------------------
Reporter: pernici | Owner: AlexGhitza
Type: enhancement | Status: new
Priority: minor | Milestone: sage-4.6
Component: basic arithmetic | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
--------------------------------+-------------------------------------------
Comment(by ylchapuy):
I think I got an even faster implementation.
I'm sorry but I don't have a development Sage handy for the next days, so
I just put the code here.
If you want to make a clean patch with this, go ahead; otherwise, I will
do it in some days when I'm back home.
{{{
def multinomial_coefficients(m, n):
if m == 2:
return binomial_coefficients(n)
t = [n] + [0] * (m - 1)
r = {tuple(t): 1}
if n:
p0 = 0 # leftmost nonzero position
else:
p0 = m
# enumerate tuples in co-lex order
while p0 < m - 1:
# compute next tuple
j = p0
tj = t[j]
t[j+1] += 1
if j:
t[0] = tj
t[j] = 0
if tj > 1:
p0 = 0
start = 1
else:
p0 += 1
start = p0
# compute the value
v = 0
for k in xrange(start, m):
if t[k]:
t[k] -= 1
v += r[tuple(t)]
t[k] += 1
t[0] -= 1
r[tuple(t)] = (v * tj) // (n - t[0])
return r
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9941#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
