permutations - fast & with low memory consumption?

[Paul McGuire]

"Christian Meesters" <meesters at uni-mainz.de> wrote in message 
news:em8tlg$9ka$1 at news1.zdv.uni-mainz.de...
> 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:
>
> def permute(atomlist, size = 2):
>    """
>        returns a list of atoms grouped by two
>    """
>    if not size or not atomlist:
>        return [atomlist[:0]]
>    else:
>        result = list()
>        for i in xrange(len(atomlist)):
>            pick = atomlist[i:i+1] # sequence slice
>            remainder = atomlist[:i] + atomlist[i+1:] # keep [:i] part
>            for x in __permute(remainder, size = size - 1):
>                result.append(pick + x)
>        return result
>
> Does anybody know a solution which consumes less memory and is possibly
> faster, perhaps using generator expressions? All my attempts so far 
> failed.
>
> Any help appreciated!
> TIA
> Christian

Am I correct in understanding that you want to find the permutations of a 
list up to 1e5 elements in length, taken 2 or more at a time?  FYI, P(1e5,2) 
evaluates to just under 10 billion, so I would suggest some implementation 
other than a function that returns a list of all of the permutations (think 
"generator").

Wikipedia also includes a pseudocode algorithm for computing permutations 
(http://en.wikipedia.org/wiki/Permutation), but beware, it appears to be 
1-based.

-- Paul