Speeding up permutations generation

[Stefan Behnel]

Ian Kelly schrieb am 06.03.2015 um 18:13:
> On Fri, Mar 6, 2015 at 1:24 AM, Abhiram R 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.
>>
>> 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.

Well, one obvious "optimisation" in a case like this is to change the order
in which permutations are returned. If processing all of them is
infeasible, then being able to control which ones will be processed can be
a crucial property of a "better" algorithm.

Stefan