interesting exercise

[Charles Sanders]

Michael Tobis wrote:
> Here is the bloated mess I came up with. I did see that it had to be
> recursive, and was proud of myself for getting it pretty much on the
> first try, but the thing still reeks of my sorry old fortran-addled
> mentality.

Recursion is not necessary, but is much, much clearer.

Here is one non-recursive version from another aging
fortran programmer. I agree it is less clear than most
of the recursive alternatives. No checks for sorted
input etc, these are left as an exercise for the reader.

def permute( s, n ):
   def _perm( m, n ):
     ilist = [0]*n
     while True:
       yield ilist
       i = n-1
       while i >= 0 and ilist[i]>=m-1: i = i - 1
       if i >= 0:
         ilist = ilist[0:i] + [ilist[i]+1] + [0]*(n-i-1)
       else:
         return

   return [ ''.join([s[i] for i in ilist])
     for ilist in _perm(len(s),n) ]

print "permute('abc',2) = ", permute('abc',2)
print "len(permute('13579',3)) = ", len(permute('13579',3))

permute('abc',2) =  ['aa', 'ab', 'ac', 'ba', 'bb', 'bc',
'ca', 'cb', 'cc']
len(permute('13579',3)) =  125

or even this monstrosity ...

def permute2( s, n ):
   return [ ''.join([ s[int(i/len(s)**j)%len(s)]
     for j in range(n-1,-1,-1)])
       for i in range(len(s)**n) ]

print "permute2('abc',2) =", permute2('abc',2)
print "len(permute2('13579',3)) =", len(permute2('13579',3))

permute2('abc',2) = ['aa', 'ab', 'ac', 'ba', 'bb', 'bc',
  'ca', 'cb', 'cc']
len(permute2('13579',3)) = 125


Charles