Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #87059 > unrolled thread

Re: Speeding up permutations generation

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Speeding up permutations generation Stefan Behnel <stefan_ml@behnel.de> - 2015-03-06 21:24 +0100

#87059 — Re: Speeding up permutations generation

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

[toc] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web