[Python-ideas] Implement `itertools.permutations.__getitem__` and `itertools.permutations.index`

[Paul Moore]

On 6 May 2014 10:35, Tal Einat <taleinat at 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