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

[MRAB]

On 12/10/2013 00:49, Nick Coghlan wrote:
>
> On 12 Oct 2013 08:45, "David Mertz" <mertz at gnosis.cx
> <mailto:mertz at gnosis.cx>> wrote:
>  >
>  >
>  > I realize after reading
> http://stackoverflow.com/questions/6284396/permutations-with-unique-values
> that 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).
>
OK, here's a new implementation:

def unique_permutations(iterable, count=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 []

     items = list(iterable)

     keys = {}

     for item in items:
         keys.setdefault(item, len(keys))

     items.sort(key=keys.get)

     if count is None:
         count = len(items)

     yield from perm(items, count)