permutations - fast & with low memory consumption?

[Jack Diederich]

On Tue, Dec 19, 2006 at 03:14:51PM +0100, Christian Meesters wrote:
> Hi,
> 
> I'd like to hack a function which returns all possible permutations as lists
> (or tuples) of two from a given list. So far, I came up with this solution,
> but it turned out to be too slow for the given problem, because the list
> passed ("atomlist") can be some 1e5 items long:     
> 
[snip python]
> 
> Does anybody know a solution which consumes less memory and is possibly
> faster, perhaps using generator expressions? All my attempts so far failed.
> 

You could try the probstat module (probstat.sourceforge.net).  I use it
regularly but then again I wrote it ;)  On my rinky dink laptop just doing

import probstat
for twotup in probstat.Permutation(list('A'*10000), 2):
  pass

takes 50 seconds.  It gets much worse very quickly.  A list of only a thousand
A's takes .5 seconds.  This is because "100 choose 2" has 9900 permutations,
"1000 choose 2" has 999000, "1000 choose two" has 99990000, etc.

-Jack