[sympy] Comb (#1698)
Christopher Smith
To complement the generators of partitions, permutations and combinations which are multiset-aware, counting functions that are also multset-aware have been added, too. This bring together the variety of counting functions (like Sterling and Bell functions) to provide counts for the different combinatorical quantities:
>>> s = 'mississippi'
>>> nC(s,3)
15
>>> nP(s)
34650
>>> nP(s, 3) # permutations of length 3
53
>>> nT(s, 3) # partitions of length 3
609
>>> nT(s) # partitions of any length
6033
You can merge this Pull Request by running:
git pull https://github.com/smichr/sympy comb
Or view, comment on, or merge it at:
https://github.com/sympy/sympy/pull/1698
Commit Summary
- add nC and nP to combinatorial numbers
- new _gen_poly algorithm
- add stirling function and nT for partition enumeration
- add reduced Stirling numbers of 2nd kind
- fix errors and add more tests for coverage.
File Changes
- M sympy/combinatorics/permutations.py (4)
- M sympy/functions/combinatorial/numbers.py (400)
- M sympy/functions/combinatorial/tests/test_comb_numbers.py (113)
- M sympy/utilities/iterables.py (2)
- M sympy/utilities/tests/test_iterables.py (3)
Patch Links
—
Reply to this email directly or view it on GitHub.
Aaron Meurer
Are these names standard? Again, some references in the docstrings would be nice.
Christopher Smith
nC and nP are the TI-calculator buttons for this; I invented nT. Most of this is not from a site, it's just wrapping together the already-documented functions that compute those sorts of things. I'll get around to adding more references.
Aaron Meurer
Is that the same thing as nCr and nPr?
Christopher Smith
yes, but these are multiset-aware so you can compute nC('aabcc',3)
Julien Rioux
SymPy Bot Summary: 
Failed after merging smichr/comb (4d3db97) into master (d503614).
@smichr: Please fix the test failures.
PyPy 2.0.0-beta-1; 2.7.3-final-42: fail
Python 2.7.2-final-0: fail
Python 3.2.1-final-0: fail
Sphinx 1.1.3: pass
Docs build command: make clean && make html-errors && make latex && cd _build/latex && xelatex sympy-*.tex
Christopher Smith
@jrioux , I see there is an update to pep8 which might be useful (haven't checked it out, though):
Now optional whitespace around + - * / ** // has its own error code which is ignored by default (in agreement with new relaxed rules of PEP 8).
Julien Rioux
SymPy Bot Summary: Failed after merging smichr/comb (c0ec74f) into master (d503614).
@smichr: Please fix the test failures.
PyPy 2.0.0-beta-1; 2.7.3-final-42: fail
Python 2.7.2-final-0: fail
Python 3.2.1-final-0: fail
Sphinx 1.1.3: pass
Docs build command: make clean && make html-errors && make latex && cd _build/latex && xelatex sympy-*.tex
—
Reply to this email directly or view it on GitHub.
Aaron Meurer
SymPy Bot Summary: Failed after merging smichr/comb (277ee77) into master (8083428).
@smichr: Please fix the test failures.
Python 2.5.0-final-0: fail
Python 2.6.6-final-0: fail
Python 2.7.2-final-0: fail
Python 2.6.8-final-0: pass
Python 2.7.3-final-0: fail
PyPy 2.0.0-beta-1; 2.7.3-final-42: pass
Python 3.2.2-final-0: pass
Python 3.3.0-final-0: pass
Python 3.2.3-final-0: pass
Python 3.3.0-final-0: pass
Python 3.3.0-final-0: pass
**Sphinx 1.1.3:** pass
Christopher Smith
references have been added to the nC, nT and nP routines
Aaron Meurer
@pkrathmann2 care to review this?
Rathmann
until about January 5.
If that is too late, sorry. Otherwise, I will post something then.
On Fri, Dec 28, 2012 at 7:10 PM, Aaron Meurer <notifi...@github.com>wrote:
> @pkrathmann2 <https://github.com/pkrathmann2> care to review this?
>
> —
> Reply to this email directly or view it on GitHub<https://github.com/sympy/sympy/pull/1698#issuecomment-11746797>.
Aaron Meurer
Unless @smichr wants to build on top of this, I don't see any reason to rush. If so, let's just merge this now and you can look at it retroactively.
Christopher Smith
No rush...it can wait. Also, when the taocp multiset_partitions is available, the partitions work that I did recently will be obsolete. I just don't see a way to crack the multiset_partition counting problem in an efficient way. About everything I think of is about as costly as just generating the partitions and counting. The only thing that would be nice is if the new taocp algorithm could be modified to take a k-parts argument.