Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <CADgpKWaJkyO8yCPmTSphGjPBaCWcNUpJOwDdb7tJ-hNHPTMf4A@mail.gmail.com>
References: <CADgpKWb=q2=YEJSS1yRkgzF37nO5BNRnywm+zhcwF-MAOr6MdA@mail.gmail.com> <CALwzid=O96Jd_bwwgxOuswmW9ucoFh=4Ht1P1Msrb7POZij__w@mail.gmail.com> <CADgpKWaJkyO8yCPmTSphGjPBaCWcNUpJOwDdb7tJ-hNHPTMf4A@mail.gmail.com>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Fri, 6 Mar 2015 10:13:25 -0700
Subject: Re: Speeding up permutations generation
To: Python <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.122.1425662054.21433.python-list@python.org>
Lines: 23
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:87047

On Fri, Mar 6, 2015 at 1:24 AM, Abhiram R <abhi.darkness@gmail.com> wrote:
>
>>
>> A list of 100 elements has approximately 9.33 x 10**157 permutations.
>> If you could somehow generate one permutation every yoctosecond,
>> exhausting them would still take more than a hundred orders of
>> magnitude longer than the age of the universe.
>> --
>> https://mail.python.org/mailman/listinfo/python-list
>
>
> True that :D I may have exaggerated on the number. Let's consider something
> more practically manageable => 50 elements with a 50! permutation.
> Is there a solution now?

That's still infeasible, as others have pointed out. At one
permutation every picosecond, you'll still need 9.6 x 10**44 years.

If the size isn't that important to you and you just want a faster
implementation of permutations, you could try reimplementing it
yourself as a C extension. The stdlib implementation is already
written in C though, so unless you have a better algorithm I doubt
you'll find much room for optimization.