Comment #14 on issue 3501 by [email protected]: Missing partitions in sympy.utilities.iterables.multiset_partitions
http://code.google.com/p/sympy/issues/detail?id=3501
Thanks for your implementation of https://github.com/sympy/sympy/pull/1658, and for pointing me to the Wilf reference.
I haven't done an exhaustive regression but it is providing the correct answer on everything I have checked so far.
Using your implementation to enumerate all the possible factorings of numbers up to 12000 takes 624 seconds on my laptop. (Well, not counting the powers of primes. I had code which used integer partitions for that special case.) This is a *lot* faster than the filter method I posted in comment 11. Enumerating factoring of numbers up to 1000 takes 292 seconds with my code, and only 2 seconds with yours. The large discrepancy is surprising, since in each case we look at all the set partitions and collapse them down as needed. If the performance difference is real, it might be worth exposing the core of your code as a set partitions implementation.
Some specific comments (and sorry, if I should be commenting on the pull request itself, let me know).
1) You still have the second parameter, m, but the comment explaining what it is for has gone away.
2) Integer partitions could be special cased to use combinatorics.partitions. The difference is pretty dramatic. For example, for n=14 there are 190 million set partitions, but only 135 integer partitions.
3) Integer versus set partitions is the extreme case, but any time the multiplicity of elements is high, a proper implementation of Knuth's 7.1.2.5m is going to be much faster than finding equivalence classes of set partitions. (And to be fair, Knuth himself would not refer to 7.1.2.5m as his algorithm. He traces it back to work by Wallis in 1685.)
4) After much procrastination, I think I now have my head around 7.1.2.5m. I will see if I can produce an implementation of it, if only for my own edification. One thing that might have to be sacrificed would be the second parameter. Knuth provides, in an exercise, a version which produces partitions of at most r parts, but not exactly r parts.
-- 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.
