Comment #21 on issue 3501 by pkrathma...@gmail.com: Missing partitions in
sympy.utilities.iterables.multiset_partitions
http://code.google.com/p/sympy/issues/detail?id=3501
Hello,
I have had a chance to look at the pull request, and perform some
testing. (I see that you are adding more commits, so this is only
up-to-date as of 2c11617.)
Thanks for the commit which responds to comment 20 (and incorporates the
optimization).
First, since I am new to sympy and git, here is what I did to get
access to your changed files:
git remote add smichr git://github.com/smichr/sympy.git
git fetch smichr
git checkout -b kbins smichr/kbins
If this is wrong, that might explain inconsistencies in the comments
below (and please let me know, so I can fix my process).
Overall, the code looks very clean.
I paid particular attention to _set_partitions. I agree that this
implementation is about as good as possible for set
partitions in the m=None case. After all, it is amortized constant
time per partition vector returned, and it is hard to do better than
constant time! As used in multiset_partitions, in the the m=<number>
case, there may well be a faster approach than generating all the
patitions and filtering to get only those of the desired size. But, I
am certainly not suggesting we try for that case -- this code is
already quite elaborate, and a huge improvement over what is currently
in master.
The code for _set_partitions is short, and well commented, but the the
algorithm (and especially the data structure) is going to be
non-obvious to someone looking at it for the first time.
You *might* consider adding something like the following to the
comments/doc:
This algorithm is similar to, and solves the same problem as,
Algorithm 7.2.1.5H, from volume 4A of Knuth's The Art of Computer
Programming. Knuth uses the term "restricted growth string" where
this code refers a "partition vector". In each case, the meaning is
the same: the value in the ith element of the vector specifies to
which part the ith set element is to be assigned.
At the lowest level, this code implements an n-digit big-endian
counter (stored in the array q) which is incremented (with carries) to
get the next partition in the sequence. A special twist is that a
digit is constrained to be at most one greater than the maximum of all
the digits to the left of it. The array b maintains this maximum, so
that the code can efficiently decide when a digit can be incremented
in place or whether it needs to be reset to 0 and trigger a carry to
the next digit. The enumeration starts with all the digits 0 (which
corresponds to all the set elements being assigned to the same 0th
part), and ends with 0123...n, which corresponds to each set element
being assigned to a different, singleton, part.
---------------------------
The helper function _partition provides similar, but lighter-weight
functionality to that provided by the classmethod
combinatorics.partitions.Partition.from_rgs(). Perhaps worth a
cross-reference?
I also wrote a tester to sanity check. I am attaching it to this
post. Perhaps something like test_partitions() is worth incorporating
into the tests? The one-off tests at the bottom of this most
likely duplicate tests you already have.
-----------------
multiset_partitions
--> docstring
The analytical discussion under "Counting"
These formulas only apply in the set case. Multisets are more
complicated... perhaps:
If the input is a set (no repeated elements), the number of partitions
returned is given by the bell number ...
----------------
I looked briefly at the new multiset_combinations and
multiset_permutations and didn't see anything to argue with. (Except
of course the TODO comment in multiset_combinations).
Misc - combinatorics.RGS_enum() seems to be computing the same thing
as bell()? Worth a cleanup or cross reference?
Attachments:
tester_partitions.py 1.7 KB
--
You received this message because you are subscribed to the Google Groups
"sympy-patches" group.
To post to this group, send email to sympy-patches@googlegroups.com.
To unsubscribe from this group, send email to
sympy-patches+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
