"Christian Meesters" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > 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 -- http://mail.python.org/mailman/listinfo/python-list
