440,235 Members | 1,022 Online 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
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 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

 P: n/a En Tue, 08 May 2007 01:33:51 -0300, Steven D'Aprano 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

 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

 P: n/a On May 8, 9:31 am, Steven D'Aprano

 P: n/a

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

 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 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 coupledozen lines which I'll post later if there is interest). Is there someclever Pythonism I didn't spot? Peering into my crystal ball, I see that your algorithm does the wrongthing, and contains bugs too. You certainly don't need to partion thesequence 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 youshould just post your code here, so we can look at it?In the meantime, here's a simple generator to do permutations withrepetition: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] + tailIt doesn't do a test for the sequence containing duplicates, and I leaveit 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

 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 whicheven 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 This takes annoying past annoying to some new level of hell to whicheven 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 >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 + a else: b = nextword(word,alphabet) if b: return b + (len(word) - 1) * alphabet else: return None def allwords(length,alphabet="01"): if not validAlphabet(alphabet): raise ValueError("bad token list %s" % alphabet) word = length * alphabet 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 = *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] + *(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 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 = *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] + *(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 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 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)) = 125Charles 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 wrote: castiro...@gmail.com wrote: On May 9, 1:13 am, Charles Sanders 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. 