permutations - fast with low memory consumption?
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: permutations - fast with low memory consumption?
On 12/19/06, Christian Meesters [EMAIL PROTECTED] 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: Anything here? http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/190465 -- Cheers, Simon B [EMAIL PROTECTED] -- http://mail.python.org/mailman/listinfo/python-list
Re: permutations - fast with low memory consumption?
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 Does anybody know a solution which consumes less memory and is possibly faster, perhaps using generator expressions? All my attempts so far failed. No claims with respect to speed, but the kslice function here: http://gflanagan.net/site/python/utils/sequtils/ will give the 'k-subsets' which then need to be permuted - alternatively Google. Gerard -- http://mail.python.org/mailman/listinfo/python-list
Re: permutations - fast with low memory consumption?
Thanks Simon Gerard! I will check those exampels out. Christian PS Of course, I did google - but apparently not creative enough. -- http://mail.python.org/mailman/listinfo/python-list
Re: permutations - fast with low memory consumption?
Gerard Flanagan wrote: No claims with respect to speed, but the kslice function here: http://gflanagan.net/site/python/utils/sequtils/ will give the 'k-subsets' which then need to be permuted - alternatively Google. Maybe the function below could then do these permutations. Anton. def _sorted(seq): Return a sorted copy of seq, preserving the type. res = seq[0:0] decorated = ((x,i) for i,x in enumerate(seq)) for x,i in sorted(decorated): res += seq[i:i+1] return res def _swap_and_reverse_tail(R,i,j): Swap R[i] and R[j], reverse R[i+1:]. Returns a copy, preserving the type. a,b,c,d,e = R[:i],R[i:i+1],R[i+1:j],R[j:j+1],R[j+1:] return a+d+(c+b+e)[::-1] def permutations(seq): Generate sorted permutations of any sequence that can be indexed and sliced, preserving the type. e.g. seq can be a string, list, tuple or array. n = len(seq) if n == 1: yield seq[:] elif n = 2: R = _sorted(seq) while True: yield R i,j = n-2,n-1 while R[i] = R[i+1] : i -= 1 if i == -1: return while R[i] = R[j]: j -= 1 R = _swap_and_reverse_tail(R,i,j) def test(): seq = 'gkDr217sKGMNLPsrtqeiczxyq' P = permutations(seq) for i,x in enumerate(P): print '%s' %(x) if i == 10: break if __name__ == '__main__': test() -- http://mail.python.org/mailman/listinfo/python-list
Re: permutations - fast with low memory consumption?
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
Re: permutations - fast with low memory consumption?
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'*1), 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 , etc.
-Jack
--
http://mail.python.org/mailman/listinfo/python-list
Re: permutations - fast with low memory consumption?
From pytrix: http://www.american.edu/econ/pytrix/pytrix.py def permutationsg(lst): '''Return generator of all permutations of a list. ''' if len(lst)1: for i in range(len(lst)): for x in permutationsg(lst[:i]+lst[i+1:]): yield [lst[i]]+x else: yield lst hth, Alan Isaac -- http://mail.python.org/mailman/listinfo/python-list
