Comment #15 on issue 3501 by smi...@gmail.com: Missing partitions in sympy.utilities.iterables.multiset_partitions
http://code.google.com/p/sympy/issues/detail?id=3501
Can you explain what you mean by "exposing the core of your code as a set partitions implementation"? I think I might get it but let me explain the current situation:
iterables contains partitions and multiset_partitions. `partitions` is actually a very fast integer partition algorithm. multiset_partition handles both set and multiset partitions. So perhaps you are suggesting that partitions should be renamed integer_partitions, I expose the core of multiset_partitions as set_partitions and then use that in multiset_partitions. Yes? Perhaps a better thing to do would be to make partitions itself the doorway to all the functions. 1) if input is an integer you get integer partitions; 2) if you pass a list (or set) you get set partitions; 3) if you pass a dictionary you get multiset partitions.
Some specific comments (and sorry, if I should be commenting on the pull request itself, let me know).
On the PR is a the preferred place, but the two refer to each other so this is ok, too.
1) You still have the second parameter, m, but the comment explaining what it is for has gone away.
I'll add more description.
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.
I'm not sure this is necessary since Partitions only accepts set-like input: ```
Partition([[1,2,3,1]])
Traceback (most recent call last): ... ValueError: Partition contained duplicated elements. ```
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.)
Agreed. If you can get the routine running again it would be great to see it working. I think Knuth said something about the enduring quality of an algorithm like "you just have to see it". Well the nextequ has that quality for me...it's so simple!
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.
Great! -- 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.
