Implement `itertools.permutations.__getitem__` and `itertools.permutations.index`

[Ram Rachum]

I suggest implementing:

 - `itertools.permutations.__getitem__`, for getting a permutation by its index number, and possibly also slicing, and 

 - `itertools.permutations.index` for getting the index number of a given permutation. 

What do you think? 

Thanks,

Ram.

[Ram Rachum]

And now that I think about it, I'd also like to give it a `__len__`, and to give `itertools.product` the same treatment. What do you think? 

[Steven D'Aprano]

An intriguing idea.

range() objects also implement indexing, and len. But range() objects
have an obvious, unambiguous order: range(2, 6) *must* give 2, 3, 4, 5,
in that order, by the definition of range. Permutations aren't like
that. The order of the permutations is an implementation detail, not
part of the definition. If permutations provides indexing operations,
then the order becomes part of the interface. I'm not sure that's such a
good idea.

I think, rather that adding __getitem__ to permutations, I would rather
see a separate function (not iterator) which returns the nth
permutation.


--
Steven
_______________________________________________
Python-ideas mailing list
Python...@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

[Steven D'Aprano]

On Mon, May 05, 2014 at 09:07:27AM -0700, Ram Rachum wrote:
> And now that I think about it, I'd also like to give it a `__len__`, and to
> give `itertools.product` the same treatment. What do you think?

Consider:

p = itertools.permutations('CAT')
assert len(p) == 6

So far, that's obvious. But:

next(p)
=> returns a permutation

Now what will len(p) return? If it still returns 6, that will lead to
bugs when people check the len, but fail to realise that some of those
permutations have already been consumed. In the most extreme case, you
could have:

assert len(p) == 6
list(p) == []

which is terribly surprising.


On the other hand, if len(p) returns the number of permutations
remaining, apart from increasing the complexity of the iterator, it will
also be surprising to those who expect the length to be the total number
of permutations.

I would rather have a separate API, perhaps something like this:

p.number() # returns the total number of permutations

[Ram Rachum]

If instead of having the `permutations` object be the iterator we'd have it return an internal iterator object with __iter__, the problem would be solved.

--

---
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/in2gUQMFUzA/unsubscribe.
To unsubscribe from this group and all its topics, send an email to python-ideas...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[INADA Naoki]

> range() objects also implement indexing, and len. But range() objects
> have an obvious, unambiguous order: range(2, 6) *must* give 2, 3, 4, 5,
> in that order, by the definition of range. Permutations aren't like
> that. The order of the permutations is an implementation detail, not
> part of the definition. If permutations provides indexing operations,
> then the order becomes part of the interface. I'm not sure that's such a
> good idea.

I don't think the order of permutation is implementation detail.
Python implementations should follow CPython's documented order.

https://docs.python.org/3.4/library/itertools.html#itertools.permutations

> Permutations are emitted in lexicographic sort order. So, if the input iterable is sorted, the permutation tuples will be produced in sorted order.

--
INADA Naoki <songof...@gmail.com>

[Ethan Furman]

On 05/05/2014 03:22 PM, INADA Naoki wrote:
>> range() objects also implement indexing, and len. But range() objects
>> have an obvious, unambiguous order: range(2, 6) *must* give 2, 3, 4, 5,
>> in that order, by the definition of range. Permutations aren't like
>> that. The order of the permutations is an implementation detail, not
>> part of the definition. If permutations provides indexing operations,
>> then the order becomes part of the interface. I'm not sure that's such a
>> good idea.
>
> I don't think the order of permutation is implementation detail.
> Python implementations should follow CPython's documented order.
>
> https://docs.python.org/3.4/library/itertools.html#itertools.permutations
>
>> Permutations are emitted in lexicographic sort order. So, if the input iterable is sorted, the permutation tuples will be produced in sorted order.

What does that mean? If permutations are emitted in an order, why does the input iterable have to be ordered? What
happens if it's not?

--> list(''.join(p) for p in permutations('abc'))
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

--> list(''.join(p) for p in permutations('cab'))
['cab', 'cba', 'acb', 'abc', 'bca', 'bac']


Okay, read http://en.wikipedia.org/wiki/Lexicographical_order -- I think 'lexicographic' is not the best choice of
word... maybe positional?

--
~Ethan~

[Steven D'Aprano]

On Tue, May 06, 2014 at 07:22:56AM +0900, INADA Naoki wrote:

> I don't think the order of permutation is implementation detail.
> Python implementations should follow CPython's documented order.
>
> https://docs.python.org/3.4/library/itertools.html#itertools.permutations

Hmmm. Well, since the order of permutations is documented, I suppose my
objection is answered. In that case, it becomes a question of whether or
not there is an easy way to generate the Nth permutation without having
to iterate through the previous N-1 permutations.

> > Permutations are emitted in lexicographic sort order. So, if the
> > input iterable is sorted, the permutation tuples will be produced in
> > sorted order.

I think I know what the docs are trying to say, but I'm not sure if they
are quite saying it correctly. If the permutations are emitted in
"lexicographic sort order", that implies that they are sortable, but
that's not necessarily the case:

py> 4j > 2j
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: no ordering relation is defined for complex numbers
py> list(itertools.permutations([4j, 2j]))
[(4j, 2j), (2j, 4j)]

I think that just removing the word "sort" is sufficient: "Permutations
are emitted in lexicographic order" is meaningful, and correct, even
when the elements are not sortable.

[Tal Einat]

On Tue, May 6, 2014 at 5:39 AM, Steven D'Aprano <st...@pearwood.info> wrote:
> On Tue, May 06, 2014 at 07:22:56AM +0900, INADA Naoki wrote:
>
>> I don't think the order of permutation is implementation detail.
>> Python implementations should follow CPython's documented order.
>>
>> https://docs.python.org/3.4/library/itertools.html#itertools.permutations
>
> Hmmm. Well, since the order of permutations is documented, I suppose my
> objection is answered. In that case, it becomes a question of whether or
> not there is an easy way to generate the Nth permutation without having
> to iterate through the previous N-1 permutations.

Yes, it is possible using factorial decomposition of N.

See, for an example: http://stackoverflow.com/a/7919887/40076

- Tal Einat

[Paul Moore]

On 6 May 2014 10:35, Tal Einat <tale...@gmail.com> wrote:
>> Hmmm. Well, since the order of permutations is documented, I suppose my
>> objection is answered. In that case, it becomes a question of whether or
>> not there is an easy way to generate the Nth permutation without having
>> to iterate through the previous N-1 permutations.
>
> Yes, it is possible using factorial decomposition of N.
>
> See, for an example: http://stackoverflow.com/a/7919887/40076

For large N, this is much slower than itertools.permutations when you
only want the first few entries.

p = itertools.permutations(range(10000))
for i in range(5):
print(next(p))

vs

for i in range(5):
print(ithperm(10000, i))

The first is substantially faster.

That's not to say that ithperm isn't useful, just that its
computational complexity may be surprising if it's spelled as an
indexing operation.

Paul

[Tal Einat]

On Tue, May 6, 2014 at 3:45 PM, Paul Moore <p.f....@gmail.com> wrote:
> On 6 May 2014 10:35, Tal Einat <tale...@gmail.com> wrote:
>>> Hmmm. Well, since the order of permutations is documented, I suppose my
>>> objection is answered. In that case, it becomes a question of whether or
>>> not there is an easy way to generate the Nth permutation without having
>>> to iterate through the previous N-1 permutations.
>>
>> Yes, it is possible using factorial decomposition of N.
>>
>> See, for an example: http://stackoverflow.com/a/7919887/40076
>
> For large N, this is much slower than itertools.permutations when you
> only want the first few entries.

If someone just wants the first few entries, they probably aren't
worried about it being super fast. And if they were, they could just
iterate to get the first permutations.

As for getting anything past the first few permutations (e.g. an
arbitrary one), factorial decomposition would be faster by several
orders of magnitude than iterating from the beginning. For relatively
large permutations, iterating from the beginning could be unfeasible,
while factorial decomposition would still take far less than a second.

The real question IMO is if this is useful enough to bother including
in the stdlib. For example, I don't think it would pass the "potential
uses in the stdlib" test. Perhaps Ram (the OP) has some actual
use-cases for this?

- Tal

[Paul Moore]

On 6 May 2014 16:40, Tal Einat <tale...@gmail.com> wrote:
> The real question IMO is if this is useful enough to bother including
> in the stdlib. For example, I don't think it would pass the "potential
> uses in the stdlib" test. Perhaps Ram (the OP) has some actual
> use-cases for this?

Agreed, I suspect this is more appropriate as a utility on PyPI. But I
stand by my statement that wherever it's implemented, it should *not*
be spelled permutations(x)[N], as having indexing with a small index
being significantly slower than a few calls to next() is a nasty
performance trap for the unwary (no matter how rare it will be in
practice).

Paul

[Ram Rachum]

Hi Tal,

I'm using it for a project of my own (optimizing keyboard layout) but I can't make the case that it's useful for the stdlib. I'd understand if it would be omitted for not being enough of a common need.

[Tal Einat]

On Wed, May 7, 2014 at 8:21 PM, Ram Rachum <ram.r...@gmail.com> wrote:
> Hi Tal,
>
> I'm using it for a project of my own (optimizing keyboard layout) but I
> can't make the case that it's useful for the stdlib. I'd understand if it
> would be omitted for not being enough of a common need.

At the least, this (a function for getting a specific permutation by
lexicographical-order index) could make a nice cookbook recipe.

[Ram Rachum]

I'm probably going to implement it in my python_toolbox package. I already implemented 30% and it's really cool. It's at the point where I doubt that I want it in the stdlib because I've gotten so much awesome functionality into it and I'd hate to (a) have 80% of it stripped and (b) have the class names changed to be non-Pythonic :)

[Neil Girdhar]

I really like this and hope that it eventually makes it into the stdlib.  It's also a good argument for your other suggestion whereby some of the itertools to return Iterables rather than Iterators like range does.

Best,

Neil

[Ram Rachum]

I'll email you if/when it's released :)

_______________________________________________
Python-ideas mailing list
Python...@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

[Ram Rachum]

Hi guys,

I just wanted to give an update on this: I just released my own code that does this to PyPI: https://pypi.python.org/pypi/combi

Thanks,

Ram.

[Neil Girdhar]

Looks great!

Why did you go with "get_rapplied", "unrapplied", etc. instead of having a copy() method and using settable properties?

[Ram Rachum]

Thanks :)

Settable properties are a no-go because I wanted permutation spaces to be immutable. Since the cost of creating a new space is nil (permutations are created on-demand, not on space creation) there isn't a reason to mutate an existing space.

I don't think using a copy() method to would be very nice. But I guess it's a matter of taste.

[Neil Girdhar]

Sure, but even list has copy().  I meant settable property on the generator not on the generated permutation.

[Ram Rachum]

I'm not sure what you mean. Can you please give an example?

[Neil Girdhar]

perm_space = PermSpace(3)

perm_space.degrees = 3

list(perm_space)

perm_space.degrees = None

list(perm_space)

etc.

[Ram Rachum]

Ah, I understand. I don't like it, though I'm not sure I can really express why. One reason is that this would mean that PermSpaces would be mutable, and thus not hashable and not usable as keys in dicts and sets. It would also mean I couldn't use the `CachedProperty` pattern all over the class as I do today. So these are a couple of reasons, there might be more that didn't come to me now.

[Neil Girdhar]

Those are good reasons, thanks. :)

[Steven D'Aprano]

On Mon, Nov 17, 2014 at 09:57:55PM +0200, Ram Rachum wrote:
> Ah, I understand. I don't like it, though I'm not sure I can really express
> why. One reason is that this would mean that PermSpaces would be mutable,
> and thus not hashable and not usable as keys in dicts and sets.

I'm having trouble thinking of any reason to use a PermSpace as a dict
key or set element. Do you have a concrete example of doing so?



--
Steven

[Ram Rachum]

I actually did that in the project I made Combi for. I had a bunch of perm spaces that signified certain configurations (can't get more specific, sorry) and I wanted to find the best configuration in each space. So I had a dict from each space to the best configuration in that space.