-
-
Notifications
You must be signed in to change notification settings - Fork 649
Add Lah numbers and clean up combinatorics section #39379
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Conversation
a6c1a03
to
8a5f23d
Compare
Documentation preview for this PR (built with commit 188e64e; changes) is ready! 🎉 |
8a5f23d
to
dd56131
Compare
dd56131
to
1e9ee3e
Compare
While we're at it, maybe |
Not really, at least on my machine: sage: def lah_numbers4(n, k):
....: if k > n:
....: return 0
....: if k == 0:
....: return 0 if n else 1
....: n = Integer(n)
....: k = Integer(k)
....: a = n.factorial() // k.factorial()
....: return a**2*k // (n*(n-k).factorial())
....:
....: def lah_numbers5(n, k):
....: if k > n:
....: return 0
....: if k == 0:
....: return 0 if n else 1
....: n = Integer(n)
....: k = Integer(k)
....: a = binomial(n, k)*(n-k).factorial()
....: return a**2*k // (n*(n-k).factorial())
....:
sage: timeit('T1 = matrix([[lah_numbers4(n,k) for n in range(100)] for k in rang
....: e(100)])')
25 loops, best of 3: 9.74 ms per loop
sage: timeit('T2 = matrix([[lah_numbers5(n,k) for n in range(100)] for k in rang
....: e(100)])')
5 loops, best of 3: 116 ms per loop
sage: T1 = matrix([[lah_numbers4(n,k) for k in range(10)] for n in range(10)])
sage: T2 = matrix([[lah_numbers5(n,k) for k in range(10)] for n in range(10)])
sage: T1 == T2
True |
Apparently there's massive overhead in Try this one
(note that In my experiment, it has minimal overhead for small n and k (as in your matrix) and a few times faster for e.g. It looks impossible to have a version that calls |
Voilà! sage: def lah_numbers4(n, k):
....: if k > n:
....: return 0
....: if k == 0:
....: return 0 if n else 1
....: n = Integer(n)
....: k = Integer(k)
....: a = n.factorial() // k.factorial()
....: return a**2*k // (n*(n-k).factorial())
....:
sage: def lah_numbers6(n, k):
....: if k > n:
....: return 0
....: if k == 0:
....: return 0 if n else 1
....: n = Integer(n)
....: k = Integer(k)
....: a = n.binomial(k)
....: return a * k // n * a * (n-k).factorial()
....:
sage: timeit('T1 = matrix([[lah_numbers4(n,k) for n in range(100)] for k in range(100)])')
25 loops, best of 3: 9.36 ms per loop
sage: timeit('T1 = matrix([[lah_numbers6(n,k) for n in range(100)] for k in range(100)])')
25 loops, best of 3: 11.1 ms per loop
sage: timeit('T1 = matrix([[lah_numbers4(10000+n,10000+k) for n in range(100)] for k in range(100)])')
5 loops, best of 3: 1.91 s per loop
sage: timeit('T2 = matrix([[lah_numbers6(10000+n,10000+k) for n in range(100)] for k in range(100)])')
25 loops, best of 3: 20.7 ms per loop
sage: timeit('T1 = matrix([[lah_numbers4(10000+n,k) for n in range(100)] for k in range(100)])')
5 loops, best of 3: 10.7 s per loop
sage: timeit('T2 = matrix([[lah_numbers6(10000+n,k) for n in range(100)] for k in range(100)])')
5 loops, best of 3: 2.19 s per loop Nice! |
260df5f
to
42ef17b
Compare
42ef17b
to
02e13e9
Compare
b5d05e2
to
44c3dc1
Compare
44c3dc1
to
7a10747
Compare
5c38935
to
1ee62d8
Compare
@fchapoton As you currently seem to be in the "combinat" section, would you review this PR? This PR touches many files in the directory The new code for Lah numbers was, I think, already reviewed by @user202729. |
Resolved merge conflicts. |
I must say that I am not convinced at all by the necessity to have all titles in lower cap. |
Currently we have different styles mixed, even in the same section. It looks untidy to me. For example, see https://doc-release--sagemath.netlify.app/html/en/reference/structure/ I am making efforts to make the style consistent, in a long term. |
@fchapoton Still not convinced at all? What is your opinion on the problem of "different styles mixed"? |
Sorry, but there is only epsilon chance that I will ever review something that changes 174 files. |
As you perhaps know, most of them are trivial "lower caps" changes for titles or minor stylistic edits. |
OK. Thanks for your previous review. |
Thanks for the review and for your fast formula for Lah numbers! |
According to the Wikipedia article https://en.wikipedia.org/wiki/Lah_number, a formula that computes the Lah number$L(n,k)$ , also called the Stirling numbers of the third kind, is
but the most efficient form of the formula seems to be
contributed by @user202729.
Long time ago, #17161 proposed yet another formula that gives$L(n,k)$ for all integers $n,k$ . But that formula is extremely slow when implemented in Sage. Like existing functions for Stirling numbers, we only support the main case where $n$ and $k$ are nonnegative.
After this PR, we may close #17161, #17159, #17123 since we do not intend to support the negative$k$ case for combinatorial functions, which is I think only of minor interest and in controversy.
I made some cosmetic changes to the file
src/sage/combinat/combinat.py
, mostly for user friendliness.While at it, I ended up making extensive changes to index pages of the combinatorics section, for tidiness. In particular,
and also fixed #17421.
📝 Checklist
⌛ Dependencies