sympy/sympy — pull request #1848 by rathmann (2013-02-28 20:57:51+00:00)
Title: First pass at integrating Knuth's algorithm M into multiset_partitions

iterables/multiset_partitions.

On branch 3563_multiset
Changes to be committed:
modified: sympy/utilities/iterables.py

Author: rathmann

This is in partial response to http://code.google.com/p/sympy/issues/detail?id=3563 "Implement faster combinatorial enumeration algorithms".

I will update that issue report with an updated copy of multiset_partitions_taocp.py, which is what I intend to mine for inclusion into sympy. There is quite a bit of code here. So, since this is my first sympy pull request, I was thinking I would start with this part, and then depending on reviewer input, merge in additional functionality as appropriate.

Here is what I have:

**multiset_partions_taocp()** - this is what is in the pull request right now.

This is a free-standing leaf function, and implements Knuth's algorithm M. I tried to stay pretty close to Knuth's psuedocode, subject to the restrictions of Python (no GOTO statements).

My personal opinion is that the code is pretty clean, (subject to review, of course) and that the main issue is where it belongs, how to comment it, and wire it into the user-level multiset_partitions routine. It needs tests and docstrings.

I also have, in the updated source file, a new class, **MultisetPartitionEnumerator**. This class refactors Knuth's monolithic routine into a number of methods (initialize_enumeration, decrement_part, spread_part_multiplicity, and enum_all). The enum_all() method provides the same interface and functionality as multiset_partions_taocp(). I find this refactoring easier to understand and work with, but there is no reason for an end user to want to use it -- it is about twice as slow as the original.

However, the class adds a number of extensions, which can be useful:

* **enum_small(self, multiplicities, ub)** - enumerate partions with no more than ub parts
* **enum_large(self, multiplicities, lb)** - enumerate the partitions of a multiset with lb < num(parts)
* **enum_range(self, multiplicities, lb, ub)** - enumerate with lb < num(pars) <= ub

Where **enum_range()** could be used to implement the m parameter of multiset_partitions(). None of these use filtering, and so these methods can be quite a bit more efficient than enumerating all the partitions, and discarding those of the wrong size.

In addition, the class implements **count_partitions_dp()**, which counts multiset partitions, in a way which is potentially a lot faster than enumerating them.

The code in MultisetPartitionEnumerator is quite a bit less mature than multiset_partions_taocp. I figure I will clean it up as I merge it into the pull request, and once I have a better understanding of the issues of code location, user interface, etc.