permutations - fast & with low memory consumption?

[Christian Meesters]

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

 

[Christian Meesters]

Thanks Simon & Gerard!

I will check those exampels out.

Christian

PS Of course, I did google - but apparently not creative enough.

 

[Gerard Flanagan]

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:

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

 

[Simon Brunning]

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

 

[Anton Vredegoor]

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 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 >= R[i+1] :
i -= 1
if i == -1:
return
while R >= R[j]:
j -= 1
R = _swap_and_reverse_tail(R,i,j)

def test():
seq = 'gkDr217sKGMNLPsrtqeiczxyqqqqq'
P = permutations(seq)
for i,x in enumerate(P):
print '%s' %(x)
if i == 10:
break

if __name__ == '__main__':
test()

 

[Paul McGuire]

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

 

[Jack Diederich]

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

 

[Alan Isaac]

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]+x
else:
yield lst

hth,
Alan Isaac