How to generate all permutations of a string?

[Boris Borcic]

I wrote:
> Another generator solution, based on computing a permutation from its 
> rank according to some natural order. Written for strings.
> 
> def perms(s) :
>     def nth(n,L,k=1) :
>         if k>len(L) :
>             if n :
>                 raise StopIteration
>             return ''
>         return nth(n/k,L,k+1)+L.pop(n%k)
>     for n in xrange(1<<30) :
>         yield nth(n,list(s))

Same principle, simpler (no recursion, no helper func, less tokens, easier to 
read) :

def perms(s) :
     for n in xrange(1<<30) :
         R,L = [],list(s)
         while L :
             n,k = divmod(n,len(L))
             R.append(L.pop(k))
         if n : break
         yield ''.join(R)

Or if you *really* prefer lisp-style recursions, here is the solution as a 
single lambda that returns a tuple of strings (not a generator as above)

perms = lambda *S : \
             (len(S)>=len(S[0]) and S[0]==S[-1]) \
             and S[min(1,len(S)-1):] \
             or perms(''.join(L.pop(k)
                              for n,L in [[len(S),list(S[-1])]]
                              for _ in S[0]
                              for n,k in [divmod(n,len(L))]
                              )
                      ,*S)