By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,235 Members | 1,022 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,235 IT Pros & Developers. It's quick & easy.

interesting exercise

P: n/a
I want a list of all ordered permutations of a given length of a set
of tokens. Each token is a single character, and for convenience, they
are passed as a string in ascending ASCII order.

For example

permute("abc",2)

should return ["aa","ab","ac","ba","bb","bc","ca","cb","cc"]

and permute("13579",3) should return a list of 125 elements
["111","113", ... ,"997","999"]

permute("axc",N) or permute("2446",N) should raise ValueError as the
alphabet is not strictly sorted.

I have a reasonably elegant solution but it's a bit verbose (a couple
dozen lines which I'll post later if there is interest). Is there some
clever Pythonism I didn't spot?

thanks
mt

May 8 '07 #1
Share this Question
Share on Google+
24 Replies


P: n/a
Michael Tobis wrote:
I want a list of all ordered permutations of a given length of a set
of tokens. Each token is a single character, and for convenience, they
are passed as a string in ascending ASCII order.

For example

permute("abc",2)

should return ["aa","ab","ac","ba","bb","bc","ca","cb","cc"]

and permute("13579",3) should return a list of 125 elements
["111","113", ... ,"997","999"]

permute("axc",N) or permute("2446",N) should raise ValueError as the
alphabet is not strictly sorted.

I have a reasonably elegant solution but it's a bit verbose (a couple
dozen lines which I'll post later if there is interest). Is there some
clever Pythonism I didn't spot?

thanks
mt
1. You oughtta go ahead and post it.
2. Have you checked out xpermutations?

http://aspn.activestate.com/ASPN/Coo.../Recipe/190465

James
May 8 '07 #2

P: n/a
En Tue, 08 May 2007 00:45:52 -0300, Michael Tobis <mt****@gmail.com>
escribió:
I want a list of all ordered permutations of a given length of a set
of tokens. Each token is a single character, and for convenience, they
are passed as a string in ascending ASCII order.
This is what I come, no tricks, no special optimizations, just plain
Python (including your constraints):

def permute(values, n):

def _permute(values, n):
if n==1:
for letter in values:
yield [letter]
else:
for letter in values:
for others in _permute(values, n-1):
yield [letter]+others

if not sorted(values): raise ValueError("unsorted values")
if len(set(values))!=len(values): raise ValueError("duplicate values")
return list(''.join(item) for item in _permute(values, n))

--
Gabriel Genellina

May 8 '07 #3

P: n/a
On Mon, 07 May 2007 20:45:52 -0700, Michael Tobis wrote:
I have a reasonably elegant solution but it's a bit verbose (a couple
dozen lines which I'll post later if there is interest). Is there some
clever Pythonism I didn't spot?
Peering into my crystal ball, I see that your algorithm does the wrong
thing, and contains bugs too. You certainly don't need to partion the
sequence into three sub-sequences, or do that trick with the metaclass,
and it is more efficient to use list.extend() than sum.

Hang on... stupid crystal ball... that's somebody else's code. Maybe you
should just post your code here, so we can look at it?

In the meantime, here's a simple generator to do permutations with
repetition:

def permute_with_repetitions(seq):
if len(seq) <= 1:
yield list(seq)
else:
for i, item in enumerate(seq):
for tail in permute_with_repetitions(seq[:i] + seq[i+1:]):
yield [item] + tail
It doesn't do a test for the sequence containing duplicates, and I leave
it as an exercise to do selections of fewer items.
--
Steven.
May 8 '07 #4

P: n/a
On Tue, 08 May 2007 01:21:37 -0300, Gabriel Genellina wrote:
if not sorted(values): raise ValueError("unsorted values")
sorted() doesn't return a flag telling if the values are sorted, it
returns a new list containing values sorted. So this line will raise an
exception only on an empty sequence.
--
Steven.
May 8 '07 #5

P: n/a
On May 7, 10:45 pm, Michael Tobis <mto...@gmail.comwrote:
I want a list of all ordered permutations of a given length of a set
of tokens. Each token is a single character, and for convenience, they
are passed as a string in ascending ASCII order.

For example

permute("abc",2)

should return ["aa","ab","ac","ba","bb","bc","ca","cb","cc"]

and permute("13579",3) should return a list of 125 elements
["111","113", ... ,"997","999"]

permute("axc",N) or permute("2446",N) should raise ValueError as the
alphabet is not strictly sorted.

I have a reasonably elegant solution but it's a bit verbose (a couple
dozen lines which I'll post later if there is interest). Is there some
clever Pythonism I didn't spot?

thanks
mt
Post yours.

May 8 '07 #6

P: n/a
En Tue, 08 May 2007 01:33:51 -0300, Steven D'Aprano
<st****@REMOVE.THIS.cybersource.com.auescribió:
On Tue, 08 May 2007 01:21:37 -0300, Gabriel Genellina wrote:
>if not sorted(values): raise ValueError("unsorted values")

sorted() doesn't return a flag telling if the values are sorted, it
returns a new list containing values sorted. So this line will raise an
exception only on an empty sequence.
Ouch!

--
Gabriel Genellina

May 8 '07 #7

P: n/a
On May 7, 11:34 pm, castiro...@gmail.com wrote:
On May 7, 10:45 pm, Michael Tobis <mto...@gmail.comwrote:
I want a list of all ordered permutations of a given length of a set
of tokens. Each token is a single character, and for convenience, they
are passed as a string in ascending ASCII order.
For example
permute("abc",2)
should return ["aa","ab","ac","ba","bb","bc","ca","cb","cc"]
and permute("13579",3) should return a list of 125 elements
["111","113", ... ,"997","999"]
permute("axc",N) or permute("2446",N) should raise ValueError as the
alphabet is not strictly sorted.
I have a reasonably elegant solution but it's a bit verbose (a couple
dozen lines which I'll post later if there is interest). Is there some
clever Pythonism I didn't spot?
thanks
mt

Post yours.
Oh well, as I'm not the first.
def p(a,b):
if list( a ) != sorted( list( a ) ): raise ValueError, "String not
ordered."
if not b: return ['']
a = sorted( set( a ) )
return [i+j for i in a for j in p(a,b-1)]

p('abc',3)
#fb: ['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc',
'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 'caa',
'cab', 'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']
p('abc',2)
#fb: ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']
len(p("13579",3))
#fb: 125
edit()

May 8 '07 #8

P: n/a
On May 7, 11:42 pm, castiro...@gmail.com wrote:
On May 7, 11:34 pm, castiro...@gmail.com wrote:
On May 7, 10:45 pm, Michael Tobis <mto...@gmail.comwrote:
I want a list of all ordered permutations of a given length of a set
of tokens. Each token is a single character, and for convenience, they
are passed as a string in ascending ASCII order.
For example
permute("abc",2)
should return ["aa","ab","ac","ba","bb","bc","ca","cb","cc"]
and permute("13579",3) should return a list of 125 elements
["111","113", ... ,"997","999"]
permute("axc",N) or permute("2446",N) should raise ValueError as the
alphabet is not strictly sorted.
I have a reasonably elegant solution but it's a bit verbose (a couple
dozen lines which I'll post later if there is interest). Is there some
clever Pythonism I didn't spot?
thanks
mt
Post yours.

Oh well, as I'm not the first.
[working solution snip]
Or even,
def p(a,b):
if list( a ) != sorted( list( a ) ): raise ValueError, "String not
ordered."
if not b: return ['']
return [i+j for i in list(a) for j in p(a,b-1)]

p('abc',3)
#fb: ['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc',
'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 'caa',
'cab', 'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']
p('abc',2)
#fb: ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']
len(p("13579",3))
#fb: 125
edit()

May 8 '07 #9

P: n/a
On May 8, 9:31 am, Steven D'Aprano
<ste...@REMOVE.THIS.cybersource.com.auwrote:
On Mon, 07 May 2007 20:45:52 -0700, Michael Tobis wrote:
I have a reasonably elegant solution but it's a bit verbose (a couple
dozen lines which I'll post later if there is interest). Is there some
clever Pythonism I didn't spot?

Peering into my crystal ball, I see that your algorithm does the wrong
thing, and contains bugs too. You certainly don't need to partion the
sequence into three sub-sequences, or do that trick with the metaclass,
and it is more efficient to use list.extend() than sum.

Hang on... stupid crystal ball... that's somebody else's code. Maybe you
should just post your code here, so we can look at it?

In the meantime, here's a simple generator to do permutations with
repetition:

def permute_with_repetitions(seq):
if len(seq) <= 1:
yield list(seq)
else:
for i, item in enumerate(seq):
for tail in permute_with_repetitions(seq[:i] + seq[i+1:]):
yield [item] + tail

It doesn't do a test for the sequence containing duplicates, and I leave
it as anexerciseto do selections of fewer items.

--
Steven.
Dear Steven
I ran into your message quite accidentally while researching about
some details on 'Exercise' and thought of sharing some of my
findings.
I've read at 'http://www.medical-health-care-information.com/Health-
living/exercise/index.asp
that Swimming, cycling, jogging, skiing, aerobic dancing, walking or
any of dozens of other activities can help your heart. Whether it's
included in a structured exercise program or just part of your daily
routine, all physical activity adds up to a healthier heart.
I hope the above is of some help to you as well. Regards, Sherrybove.

May 8 '07 #10

P: n/a
<ca********@gmail.comwrote:
...
def p(a,b):
if list( a ) != sorted( list( a ) ): raise ValueError, "String not
ordered."
if not b: return ['']
return [i+j for i in list(a) for j in p(a,b-1)]
No need for 2/3 of the list(...) calls. sorted(a) and sorted(list(a))
will ALWAYS be the same sequence; "for i in a" and "for i in list(a)"
will always iterate on the same sequence [as long as you're not changing
a inside the iteration, which, in this case, you aren't].
Alex
May 8 '07 #11

P: n/a
On May 8, 12:24 am, a...@mac.com (Alex Martelli) wrote:
<castiro...@gmail.comwrote:

...
def p(a,b):
if list( a ) != sorted( list( a ) ): raise ValueError, "String not
ordered."
if not b: return ['']
return [i+j for i in list(a) for j in p(a,b-1)]

No need for 2/3 of the list(...) calls. sorted(a) and sorted(list(a))
will ALWAYS be the same sequence; "for i in a" and "for i in list(a)"
will always iterate on the same sequence [as long as you're not changing
a inside the iteration, which, in this case, you aren't].

Alex
Ah quite true. list( a ) != sorted( a ). ...for i in a for...

May 8 '07 #12

P: n/a
Michael Tobis wrote:
I want a list of all ordered permutations of a given length of a set
of tokens. Each token is a single character, and for convenience, they
are passed as a string in ascending ASCII order.

For example

permute("abc",2)

should return ["aa","ab","ac","ba","bb","bc","ca","cb","cc"]
If N is constant and small (e.g hard-coded N of 2), list comprehensions
provide a concise solution:

a = "abc"
b = [(x,y) for x in a for y in a]
c = ["".join(z) for z in b]
print b
print c

Gives:

[('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', ' a'), ('c',
'b'), ('c', 'c')]

['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']

Cheers,
Chris
May 8 '07 #13

P: n/a
sherry wrote:
On May 8, 9:31 am, Steven D'Aprano
<ste...@REMOVE.THIS.cybersource.com.auwrote:
>On Mon, 07 May 2007 20:45:52 -0700, Michael Tobis wrote:
>>I have a reasonably elegant solution but it's a bit verbose (a couple
dozen lines which I'll post later if there is interest). Is there some
clever Pythonism I didn't spot?
Peering into my crystal ball, I see that your algorithm does the wrong
thing, and contains bugs too. You certainly don't need to partion the
sequence into three sub-sequences, or do that trick with the metaclass,
and it is more efficient to use list.extend() than sum.

Hang on... stupid crystal ball... that's somebody else's code. Maybe you
should just post your code here, so we can look at it?

In the meantime, here's a simple generator to do permutations with
repetition:

def permute_with_repetitions(seq):
if len(seq) <= 1:
yield list(seq)
else:
for i, item in enumerate(seq):
for tail in permute_with_repetitions(seq[:i] + seq[i+1:]):
yield [item] + tail

It doesn't do a test for the sequence containing duplicates, and I leave
it as anexerciseto do selections of fewer items.

--
Steven.

Dear Steven
I ran into your message quite accidentally while researching about
some details on 'Exercise' and thought of sharing some of my
findings.
I've read at 'http://www.medical-health-care-information.com/Health-
living/exercise/index.asp
that Swimming, cycling, jogging, skiing, aerobic dancing, walking or
any of dozens of other activities can help your heart. Whether it's
included in a structured exercise program or just part of your daily
routine, all physical activity adds up to a healthier heart.
I hope the above is of some help to you as well. Regards, Sherrybove.
This takes annoying past annoying to some new level of hell to which
even satan himself wouldn't venture.
May 8 '07 #14

P: n/a
On Mon, 2007-05-07 at 22:20 -0700, sherry wrote:
On May 8, 9:31 am, Steven D'Aprano
<ste...@REMOVE.THIS.cybersource.com.auwrote:
[snip Steven's response about a programming exercise...]

[snip Sherrybove's spam about physical exercise...]
And today's award for the most conspicuous failure of the Turing test
goes to the Spambot posting as Sherrybove! (*applause*) Fortunately,
it's not programmed to deliver acceptance speeches, so it will accept
the award silently.

I-know-this-isn't-on-topic-either-but-I-couldn't-resist'ly yours,

Carsten.
May 8 '07 #15

P: n/a
On Tue, 08 May 2007 10:22:05 +0000, James Stroud wrote:
This takes annoying past annoying to some new level of hell to which
even satan himself wouldn't venture.
And thank you for sharing that piece of spam with us again. It was so much
less enjoyable to see it the second time.

Seriously James, with more and more people using automated spam filters,
it might not be such a wise idea to keep having your name associated with
spam content.
--
Steven.

May 8 '07 #16

P: n/a
Steven D'Aprano wrote:
On Tue, 08 May 2007 10:22:05 +0000, James Stroud wrote:

>>This takes annoying past annoying to some new level of hell to which
even satan himself wouldn't venture.


And thank you for sharing that piece of spam with us again. It was so much
less enjoyable to see it the second time.

Seriously James, with more and more people using automated spam filters,
it might not be such a wise idea to keep having your name associated with
spam content.

Thank you for the tip.

James
May 8 '07 #17

P: n/a
On May 8, 3:55 pm, James Stroud <jstr...@mbi.ucla.eduwrote:
Steven D'Aprano wrote:
On Tue, 08 May 2007 10:22:05 +0000, James Stroud wrote:
>This takes annoying past annoying to some new level of hell to which
even satan himself wouldn't venture.
And thank you for sharing that piece of spam with us again. It was so much
less enjoyable to see it the second time.
Seriously James, with more and more people using automated spam filters,
it might not be such a wise idea to keep having your name associated with
spam content.

Thank you for the tip.

James
We also have:

p=lambda a,n: [ ''.join( y ) for y in eval('[%%s %s]'%' '.join(['for x
%i in a'%i for i in range(n)]) %'(%s)'%','.join(['x%i'%i for i in
range(n)]) ) ]
p('abc',2)
#fb: ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']
len(p('13579',3))
#fb: 125
edit()

File under obscurities. acb

May 8 '07 #18

P: n/a
On May 8, 4:55 pm, castiro...@gmail.com wrote:
On May 8, 3:55 pm, James Stroud <jstr...@mbi.ucla.eduwrote:
Steven D'Aprano wrote:
On Tue, 08 May 2007 10:22:05 +0000, James Stroud wrote:
>>This takes annoying past annoying to some new level of hell to which
>>even satan himself wouldn't venture.
And thank you for sharing that piece of spam with us again. It was so much
less enjoyable to see it the second time.
Seriously James, with more and more people using automated spam filters,
it might not be such a wise idea to keep having your name associated with
spam content.
Thank you for the tip.
James

We also have:

p=lambda a,n: [ ''.join( y ) for y in eval('[%%s %s]'%' '.join(['for x
%i in a'%i for i in range(n)]) %'(%s)'%','.join(['x%i'%i for i in
range(n)]) ) ]
p('abc',2)
#fb: ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']
len(p('13579',3))
#fb: 125
edit()

File under obscurities. acb
Slightly clearer:
p=lambda a,n:[ ''.join( y ) for y in eval('[(%s) %s]'%(','.join(['x
%i'%i for i in range(n)]),' '.join(['for x%i in a'%i for i in
range(n)])))]
p('abc',2)
#fb: ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']
len(p('13579',3))
#fb: 125
edit()

where for n=4:
('[(%s) %s]'%(','.join(['x%i'%i for i in range(n)]),' '.join(['for x%i
in a'%i for i in range(n)])))
#fb: '[(x0,x1,x2,x3) for x0 in a for x1 in a for x2 in a for x3 in a]'

May 8 '07 #19

P: n/a
Thanks castironpi and alex, for this:

def p(a,b):
if not b: return ['']
return [i+j for i in a for j in p(a,b-1)]

That is a thing of beauty! As usual you guys didn't disappoint.

(Validity check of alphabet removed; you didn't check for duplicate
characters.)

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.

def validAlphabet(alphabet):
if not isinstance(alphabet,str):
return False
if len(alphabet) 256:
return False
for index in range(len(alphabet)-1):
if not alphabet[index] < alphabet[index+1]:
return False
return True

def nextword(word,alphabet):
if len(word) == 1:
index = alphabet.find(word)
if index < 0:
raise ValueError("bad token found %s" % word)
if index == len(alphabet) -1:
return None
else:
return alphabet[index+1]
else:
a = nextword(word[1:],alphabet)
if a:
return word[0] + a
else:
b = nextword(word[0],alphabet)
if b:
return b + (len(word) - 1) * alphabet[0]
else:
return None

def allwords(length,alphabet="01"):
if not validAlphabet(alphabet):
raise ValueError("bad token list %s" % alphabet)
word = length * alphabet[0]
result = [word]
while word < length * alphabet[-1]:
word = nextword(word,alphabet))
result.append(word)
return result

######

if __name__ == "__main__":
for item in allwords(5,"abc"):
print item

May 9 '07 #20

P: n/a
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
May 9 '07 #21

P: n/a
On May 9, 1:13 am, Charles Sanders <C.delete_this.Sand...@BoM.GOv.AU>
wrote:
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
Could you explain, this one, actually? Don't forget StopIteration.

May 9 '07 #22

P: n/a
On May 9, 2:41 pm, castiro...@gmail.com wrote:
On May 9, 1:13 am, Charles Sanders <C.delete_this.Sand...@BoM.GOv.AU>
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

May 9 '07 #23

P: n/a
ca********@gmail.com wrote:
On May 9, 1:13 am, Charles Sanders <C.delete_this.Sand...@BoM.GOv.AU>
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
May 10 '07 #24

P: n/a
On May 9, 7:49 pm, Charles Sanders <C.delete_this.Sand...@BoM.GOv.AU>
wrote:
castiro...@gmail.com wrote:
On May 9, 1:13 am, Charles Sanders <C.delete_this.Sand...@BoM.GOv.AU>
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.

May 10 '07 #25

This discussion thread is closed

Replies have been disabled for this discussion.