[Python-ideas] Fwd: Extremely weird itertools.permutations

Neil Girdhar mistersheik at gmail.com
Sat Oct 12 01:53:31 CEST 2013


Yes, that's all true.  I want to suggest that the efficient unique
permutations solution is very important to have.  Sortable sequences are
very common. There are itertools routines that only work with =-comparable
elements (e.g. groupby), so it's not a stretch to have a permutations that
is restricted to <-comparable elements.

Best,
Neil


On Fri, Oct 11, 2013 at 7:49 PM, Nick Coghlan <ncoghlan at gmail.com> wrote:

>
> On 12 Oct 2013 08:45, "David Mertz" <mertz at gnosis.cx> wrote:
> >
> >
> > I realize after reading
> http://stackoverflow.com/questions/6284396/permutations-with-unique-valuesthat my version was ALMOST right:
> >
> > def nonredundant_permutations(seq, r=None):
> >     last = ()
> >     for perm in permutations(sorted(seq), r):
> >         if perm > last:
> >             yield perm
> >             last = perm
> >
> > I can't look only for inequality, but must use the actual comparison.
> >
> > >>> ["".join(x) for x in nonredundant_permutations('aaabb',3)]
> > ['aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba']
> > >>> list(nonredundant_permutations([F(3,1), D(3.0), 3.0]))
> > [(Fraction(3, 1), Decimal('3'), 3.0)]
> >
> > Of course, this approach DOES rely on the order in which
> itertools.permutations() returns values.  However, it's a bit more compact
> than MRAB's version.
>
> As there is no requirement that entries in a sequence handled by
> itertools.permutations be sortable, so the original question of why this
> isn't done by default has been answered (the general solution risks
> consuming too much memory, while the memory efficient solution constrains
> the domain to only sortable sequences).
>
> Cheers,
> Nick.
>
> >
> >
> >
> >
> > On Fri, Oct 11, 2013 at 3:23 PM, Neil Girdhar <mistersheik at gmail.com>
> wrote:
> >>
> >> Beautiful!!
> >>
> >>
> >> On Fri, Oct 11, 2013 at 6:19 PM, MRAB <python at mrabarnett.plus.com>
> wrote:
> >>>
> >>> On 11/10/2013 23:03, David Mertz wrote:
> >>>>
> >>>> Bummer.  You are right, Neil.  I saw MRAB's suggestion about sorting,
> >>>> and falsely thought that would be general; but obviously it's not.
> >>>>
> >>>> So I guess the question is whether there is ANY way to do this without
> >>>> having to accumulate a 'seen' set (which can grow to size N!).  The
> >>>> answer isn't jumping out at me, but that doesn't mean there's not a
> way.
> >>>>
> >>>> I don't want itertools.permutations() to do "equality filtering", but
> >>>> assuming some other function in itertools were to do that, how could
> it
> >>>> do so algorithmically? Or whatever, same question if it is
> >>>> itertools.permutations(seq, distinct=True) as the API.
> >>>>
> >>> Here's an implementation:
> >>>
> >>> def unique_permutations(iterable, count=None, key=None):
> >>>     def perm(items, count):
> >>>         if count:
> >>>             prev_item = object()
> >>>
> >>>             for i, item in enumerate(items):
> >>>                 if item != prev_item:
> >>>                     for p in perm(items[ : i] + items[i + 1 : ], count
> - 1):
> >>>                         yield [item] + p
> >>>
> >>>                 prev_item = item
> >>>
> >>>         else:
> >>>             yield []
> >>>
> >>>     if key is None:
> >>>         key = lambda item: item
> >>>
> >>>     items = sorted(iterable, key=key)
> >>>
> >>>     if count is None:
> >>>         count = len(items)
> >>>
> >>>     yield from perm(items, count)
> >>>
> >>>
> >>> And some results:
> >>>
> >>> >>> print(list("".join(x) for x in unique_permutations('aaabb', 3)))
> >>> ['aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba']
> >>> >>> print(list(unique_permutations([0, 'a', 0], key=str)))
> >>> [[0, 0, 'a'], [0, 'a', 0], ['a', 0, 0]]
> >>>
> >>>
> >>> _______________________________________________
> >>> Python-ideas mailing list
> >>> Python-ideas at python.org
> >>> https://mail.python.org/mailman/listinfo/python-ideas
> >>>
> >>> --
> >>>
> >>> --- You received this message because you are subscribed to a topic in
> the Google Groups "python-ideas" group.
> >>> To unsubscribe from this topic, visit
> https://groups.google.com/d/topic/python-ideas/dDttJfkyu2k/unsubscribe.
> >>> To unsubscribe from this group and all its topics, send an email to
> python-ideas+unsubscribe at googlegroups.com.
> >>> For more options, visit https://groups.google.com/groups/opt_out.
> >>
> >>
> >>
> >> _______________________________________________
> >> Python-ideas mailing list
> >> Python-ideas at python.org
> >> https://mail.python.org/mailman/listinfo/python-ideas
> >>
> >
> >
> >
> > --
> > Keeping medicines from the bloodstreams of the sick; food
> > from the bellies of the hungry; books from the hands of the
> > uneducated; technology from the underdeveloped; and putting
> > advocates of freedom in prisons.  Intellectual property is
> > to the 21st century what the slave trade was to the 16th.
> >
> > _______________________________________________
> > Python-ideas mailing list
> > Python-ideas at python.org
> > https://mail.python.org/mailman/listinfo/python-ideas
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20131011/5029baa6/attachment.html>


More information about the Python-ideas mailing list