permutations - fast & with low memory consumption?

[Anton Vredegoor]

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 = 'gkDr217sKGMNLPsrtqeiczxyqqqqq'
     P = permutations(seq)
     for i,x in enumerate(P):
         print '%s' %(x)
         if i == 10:
             break

if __name__ == '__main__':
     test()