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

[David Mertz]

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'?

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'

There's no problem doing this with itertools.permutations:

    >>> 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])]

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.


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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20131011/7d8f8b55/attachment.html>