Awesome. Following the "if you give a bear a cookie he'll ask for a glass
of milk principle" can we use these algorithms to efficiently only produce
unique sets in the commutative case?
E.g. can we turn
>>> for p in kbin(range(3), 2, ordered=False):
... print p
...
[(0,), (1, 2)]
[(0,), (2, 1)]
[(1,), (0, 2)]
[(1,), (2, 0)]
[(2,), (0, 1)]
[(2,), (1, 0)]
[(0, 1), (2,)]
[(0, 2), (1,)]
[(1, 0), (2,)]
[(1, 2), (0,)]
[(2, 0), (1,)]
[(2, 1), (0,)]
into
>>> for p in kbin(range(3), 2, ordered=False):
... print p
...
[(0,), (1, 2)]
[(1,), (0, 2)]
[(2,), (0, 1)]
This could be done with an ifilter but as n and k become moderately sized
this might become quite large.
On Tue, Oct 30, 2012 at 2:19 PM, Chris Smith <[email protected]> wrote:
> > The commutativity problem can be solved if this stackoverflow problem
> can be
> > solved
> >
> http://stackoverflow.com/questions/13131491/partition-n-items-into-k-bins-in-python-lazily
>
> I think you've got all you need in the treasure trove that is
> iterables. Tim Peter's routine for partitions is very fast. You just
> harness that to your sequence (commutative or non-commutative) that
> you want to partition, something like:
>
>
> def kbin(l, k, ordered=True):
> """
> Return sequence ``l`` partitioned into ``k`` bins.
> If ordered is True then the order of the items in the
> flattened partition will be the same as the order of the
> items in ``l``; if False, all permutations of the items will
> be given.
>
> Examples
> ========
>
> >>> for p in kbin(range(3), 2):
> ... print p
> ...
> [[0], [1, 2]]
> [[0, 1], [2]]
> >>> for p in kbin(range(3), 2, ordered=False):
> ... print p
> ...
> [(0,), (1, 2)]
> [(0,), (2, 1)]
> [(1,), (0, 2)]
> [(1,), (2, 0)]
> [(2,), (0, 1)]
> [(2,), (1, 0)]
> [(0, 1), (2,)]
> [(0, 2), (1,)]
> [(1, 0), (2,)]
> [(1, 2), (0,)]
> [(2, 0), (1,)]
> [(2, 1), (0,)]
>
> """
> from sympy.utilities.iterables import partitions
> from sympy.core.compatibility import permutations
>
> for p in partitions(len(l), k):
> if sum(p.values()) != k:
> continue
> for pe in permutations(p.keys()):
> rv = []
> i = 0
> for part in pe:
> for do in range(p[part]):
> j = i + part
> rv.append(l[i: j])
> i = j
> if ordered:
> yield rv
> else:
> take = [len(i) for i in rv]
> for pp in permutations(l):
> rvp = []
> ii = 0
> for t in take:
> jj = ii + t
> rvp.append(pp[ii: jj])
> ii = jj
> yield rvp
>
> --
> You received this message because you are subscribed to the Google Groups
> "sympy" 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?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"sympy" 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?hl=en.
