Status: Accepted
Owner: smi...@gmail.com
Labels: Type-Defect Priority-Medium
New issue 2485 by smi...@gmail.com: multiset_partitions
http://code.google.com/p/sympy/issues/detail?id=2485
Since multiset_partitions has been pushed but there were issues raised that
weren't addressed, I am opening this issue with those comments:
mwhansen wrote:
As I mentioned in the pull request, I don't think this algorithm is
implemented correctly. For example, if you do
list(multiset_partitions([2,2,2,2],1)), it generates the multiset
partition [[2,2,2,2]] four different times. If you're going to
overgenerate and keep track of things in a "cache", then it would be
more straightforward to just generate all set partitions and filter
that.
This appears to be fixed: I only get [[[2,2,2,2]]]
mwhansen wrote:
Some other weird things:
>>> list(multiset_partitions([1,2,2],2))
[[[1, 2], [2]], [[1], [2, 2]], None]
This is not fixed. By analogy,
>>> list(multiset_partitions([1,2,3],2))
[[[1, 2], [3]], [[1], [2, 3]], [[1, 3], [2]]]
>>> list(multiset_partitions([1,2,2],2))
[[[1, 2], [2]], [[1], [2, 2]], None]
that None should be [[1, 2], [2]]
mwhansen wrote:
Partition generated twice since caching doesn't know that the order
that the parts occur in does not matter:
>>> sage: list(multiset_partitions([2,2,2,2],2))
[[[2, 2, 2], [2]], [[2, 2], [2, 2]], [[2], [2, 2, 2]]]
This is the same way subsets works: it treats all elements as unique. There
is not an attempt to return only unique subsets/partitions.
>>> list(subsets([2,2]))
[[], [2], [2], [2, 2]]
I think that if this were needed it should be implemented through
a 'unique' keyword and a different implementation so as not to slow down
the general algorithm.
One final issue that I raise: perhaps it would be nice if the combinatoric
functions (including subsets and variations) would return tuples that could
directly be fed to sets to get the unique values. Any other thoughts on
this?
--
You received this message because you are subscribed to the Google Groups
"sympy-issues" group.
To post to this group, send email to sympy-issues@googlegroups.com.
To unsubscribe from this group, send email to
sympy-issues+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sympy-issues?hl=en.