interesting exercise

[Charles Sanders]

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>=m-1: i = i - 1
if i >= 0:
ilist = ilist[0:i] + [ilist+1] + [0]*(n-i-1)
else:
return

return [ ''.join([s 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

 

[castironpi]

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>=m-1: i = i - 1
if i >= 0:
ilist = ilist[0:i] + [ilist+1] + [0]*(n-i-1)
else:
return

return [ ''.join([s 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

Could you explain, this one, actually? Don't forget StopIteration.

 

[Michael Tobis]

On May 9, 1:13 am, Charles Sanders <[email protected]>
wrote:

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

Could you explain, this one, actually? Don't forget StopIteration.

Heh, it's cute.

Not sure what the issue is with StopIteration. He is modeling the
problem as casting an integer to base N. It's terse, but it does way
too much arithmetic and isn't very readable.

The following uses the same idea more readably and (I expect,
untested) more efficiently, if less tersely. It actually is not too
bad for real code, though I much prefer your recursive list
comprehension and will use that.

def getdigits(number,base,length,alphabet):
residual = number
result = ""
for column in range(length):
residual,digit = divmod(residual,base)
result = alphabet[digit] + result
return result

def permu(alphabet,wordlength):
total = len(alphabet)**wordlength
return [getdigits(index,len(alphabet),wordlength,alphabet)
for index in range(total)]

if __name__ == "__main__":
print permu("abc",2)
print len(permu("13579",3))

mt

 

[Charles Sanders]

On May 9, 1:13 am, Charles Sanders <[email protected]>
wrote: [snip]

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

Could you explain, this one, actually? Don't forget StopIteration.

As Michael said, simple counting in base n with the
string as the digits. No attempt at clarity or efficiency (I
did say it was a "monstrosity").

Also, as a python beginner I didn't know about divmod,
and have no idea what you (castironpi) mean by "Don't forget
StopIteration."


Charles

 

[castironpi]

On May 9, 1:13 am, Charles Sanders <[email protected]>
wrote: [snip]

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

Could you explain, this one, actually? Don't forget StopIteration.

As Michael said, simple counting in base n with the
string as the digits. No attempt at clarity or efficiency (I
did say it was a "monstrosity").

Also, as a python beginner I didn't know about divmod,
and have no idea what you (castironpi) mean by "Don't forget
StopIteration."

Charles

Please disregard. I have just learned that:
"If the generator exits without yielding another value, a
StopIteration exception is raised."
"exception StopIteration
Raised by an iterator's next() method to signal that there are no
further values."
Means normal generator termination.