Comment #11 on issue 3501 by [email protected]: Missing partitions in
sympy.utilities.iterables.multiset_partitions
http://code.google.com/p/sympy/issues/detail?id=3501
Re:posting 8.
I was going to point you to the oracle himself. Knuth still has the
fasicles on his web page. See <
www-cs-faculty.stanford.edu/~uno/fasc3b.ps.gz >.
The discussion of multiset partitions is on pages 38-40 of this file
(corresponding to pp 428-430 in the real book).
But ... there are some differences between the fascicle and the printed
version. First of all, algorithm M goes from being "simple" in the fasicle
to "fairly simple" in print :). More pertinently, he made some changes in
the code itself. Perhaps saptman (GSOC 11) was working from the fascile
and lead astray?
WRT post 9. Great! I will take a look, once I figure out how to use GIT a
bit better.
Meanwhile, for testing, here are some possibilities:
1) Multiset partitions are generalizations of integer partitions and set
partitions. As a sanity check we can verify that the multiset
implementation gives the same results on these simpler cases.
2) Multiset partitions can be implemented as a wrapper on top of set
partitions, and then filtering out the duplicates. I have attached a file
which does the wrapping, but not the filtering (yet). I can try it against
pull 1658 to verify that it gets the same answers.
3) Counting multiset partitions (comment 5) is possible, but I didn't see
an easy-to-understand formula or anything.
Thanks a lot for your attention on this bug.
Attachments:
slow_multiset_partitions.py 1.3 KB
--
You received this message because you are subscribed to the Google Groups
"sympy-issues" 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/sympy-issues?hl=en.
