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

[MRAB]

On 12/10/2013 03:36, David Mertz wrote:
> Hi MRAB,
>
> I'm confused by your implementation.  In particular, what do these lines do?
>
>      # [...]
>      items = list(iterable)
>      keys = {}
>      for item in items:
>          keys.setdefault(item, len(keys))
>      items.sort(key=keys.get)
>
> I cannot understand how these can possibly have any effect (other than
> the first line that makes a concrete list out of an iterable).
>
> We loop through the list in its natural order.  E.g. say the list is
> '[a, b, c]' (where those names are any types of objects whatsoever).
>   The loop gives us:
>
>      keys == {a:0, b:1, c:2}
>
> When we do a sort on 'key=keys.get()' how can that ever possibly change
> the order of 'items'?
>
You're assuming that no item is equal to any other.

Try this:

keys = {}
for item in [1, 2, 2.0]:
     keys.setdefault(item, len(keys))

You'll get:

keys == {1: 0, 2: 1}

because 2 == 2.0.

> There's also a bit of a flaw in that your implementation blows up if
> anything yielded by iterable isn't hashable:
>
>      >>> list(unique_permutations([ [1,2],[3,4],[5,6] ]))
>      Traceback (most recent call last):
>        File "<stdin>", line 1, in <module>
>      TypeError: unhashable type: 'list'
>
That is true, so here is yet another implementation:

----8<----------------------------------------8<----

def distinct_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 []

     hashable_items = {}
     unhashable_items = []

     for item in iterable:
         try:
             hashable_items[item].append(item)
         except KeyError:
             hashable_items[item] = [item]
         except TypeError:
             for key, values in unhashable_items:
                 if key == item:
                     values.append(item)
                     break
             else:
                 unhashable_items.append((item, [item]))

     items = []

     for values in hashable_items.values():
         items.extend(values)

     for key, values in unhashable_items:
         items.extend(values)

     if count is None:
         count = len(items)

     yield from perm(items, count)

----8<----------------------------------------8<----

It uses a dict for speed, with the fallback of a list for unhashable
items.

>
>      >>> list(permutations([[1,2],[3,4],[5,6]]))
>      [([1, 2], [3, 4], [5, 6]), ([1, 2], [5, 6], [3, 4]), ([3, 4], [1,
> 2], [5, 6]),
>      ([3, 4], [5, 6], [1, 2]), ([5, 6], [1, 2], [3, 4]), ([5, 6], [3,
> 4], [1, 2])]
>
> This particular one also succeeds with my nonredundant_permutations:
>
>      >>> list(nonredundant_permutations([[1,2],[3,4],[5,6]]))
>      [([1, 2], [3, 4], [5, 6]), ([1, 2], [5, 6], [3, 4]), ([3, 4], [1,
> 2], [5, 6]),
>      ([3, 4], [5, 6], [1, 2]), ([5, 6], [1, 2], [3, 4]), ([5, 6], [3,
> 4], [1, 2])]
>
My result is:

 >>> list(distinct_permutations([[1,2],[3,4],[5,6]]))
[[[1, 2], [3, 4], [5, 6]], [[1, 2], [5, 6], [3, 4]], [[3, 4], [1, 2], 
[5, 6]], [[3, 4], [5, 6], [1, 2]], [[5, 6], [1, 2], [3, 4]], [[5, 6], 
[3, 4], [1, 2]]]

> However, my version *DOES* fail when things cannot be compared under
> inequality:
>
>      >>> list(nonredundant_permutations([[1,2],3,4]))
>      Traceback (most recent call last):
>        File "<stdin>", line 1, in <module>
>        File "<stdin>", line 3, in nonredundant_permutations
>      TypeError: unorderable types: int() < list()
>
> This also doesn't afflict itertools.permutations.
>
My result is:

 >>> list(distinct_permutations([[1,2],3,4]))
[[3, 4, [1, 2]], [3, [1, 2], 4], [4, 3, [1, 2]], [4, [1, 2], 3], [[1, 
2], 3, 4], [[1, 2], 4, 3]]