Re: Problem with algorithm
Charles Sanders [EMAIL PROTECTED] writes: Forgive any silly mistakes I have made (I've been teaching myself python for about 1 week) but there is a moderately well known algorithm for this that extends to arbitrary lengths of both the list of alternatives and the length of the required output, and avoids deeply nested loops. s = abcd def a(n): if n==0: yield '' return for c in s: for r in a(n-1): yield c+r print list(a(3)) -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
Paul Rubin wrote: [snip] def a(n): if n==0: yield '' return for c in s: for r in a(n-1): yield c+r print list(a(3)) Of course, obvious in retrospect, recursion instead of iteration. I have yet to completely wean myself off Fortran style thinking. Charles -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
for m in test: for n in test: for o in test: for p in test: print m+n+o+p Thanx for your anwser. But if I consider about a combination of over 26 letter's list just like: abcdefssdzxcvzxcvzcv asllxcvxcbbedfgdfgdg . Need I write 26 for loops to do this? Thanx Jia LU -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
I think that this would be very silly to do. bad kung foo. The recoursion technique would be more satisfying. You sholud consider that this would take about 4 lines to write. Also be avare of the default recoursion depth in python wich is 1000. you can get and set the recoursion limit hrough importing the sys module and using getrecoursionlimit() and setrecoursionlimit(). On Apr 13, 9:16 am, Jia Lu [EMAIL PROTECTED] wrote: for m in test: for n in test: for o in test: for p in test: print m+n+o+p Thanx for your anwser. But if I consider about a combination of over 26 letter's list just like: abcdefssdzxcvzxcvzcv asllxcvxcbbedfgdfgdg . Need I write 26 for loops to do this? Thanx Jia LU -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
On Apr 13, 8:16 am, Jia Lu [EMAIL PROTECTED] wrote: for m in test: for n in test: for o in test: for p in test: print m+n+o+p Thanx for your anwser. But if I consider about a combination of over 26 letter's list just like: abcdefssdzxcvzxcvzcv asllxcvxcbbedfgdfgdg . Need I write 26 for loops to do this? Thanx Jia LU Try this: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/502199 You could then write something like: import string for thiscomb in comb2( *([string.lowercase]*26) ): ... Mind you, it generates a lot of combinations. - Paddy. -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
azrael wrote: I think that this would be very silly to do. bad kung foo. The recoursion technique would be more satisfying. You sholud consider that this would take about 4 lines to write. Also be avare of the default recoursion depth in python wich is 1000. you can get and set the recoursion limit hrough importing the sys module and using getrecoursionlimit() and setrecoursionlimit(). Well, you'd have to spell sys.getrecursionlimit() correctly, but yes ;) At least in the past, raising the recursion limit past a certain point would result in the CPython interpreter crashing, so it's not completely scalable. -- Michael Hoffman -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
sorry for the bad grammar. I didn't investigate the StackLess Python, but as I have been reading about it (so if it was correct), the recursionlimit should not be the problem using StackLess Python. From my expirience with python and recursions, it works well to the depth of about 200 to 500 (depending od algorithm and purpose). I think that in this case it should work well with about 500. If you need a bigger string, then lett it repeat and merge the different strings. You could also generate multidimensional hash. Best Regards On Apr 13, 2:24 pm, Michael Hoffman [EMAIL PROTECTED] wrote: azrael wrote: I think that this would be very silly to do. bad kung foo. The recoursion technique would be more satisfying. You sholud consider that this would take about 4 lines to write. Also be avare of the default recoursion depth in python wich is 1000. you can get and set the recoursion limit hrough importing the sys module and using getrecoursionlimit() and setrecoursionlimit(). Well, you'd have to spell sys.getrecursionlimit() correctly, but yes ;) At least in the past, raising the recursion limit past a certain point would result in the CPython interpreter crashing, so it's not completely scalable. -- Michael Hoffman -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
Jia Lu wrote: for m in test: for n in test: for o in test: for p in test: print m+n+o+p Thanx for your anwser. But if I consider about a combination of over 26 letter's list just like: abcdefssdzxcvzxcvzcv asllxcvxcbbedfgdfgdg . Need I write 26 for loops to do this? Thanx Jia LU Your new example uses 20-byte strings anyway, so to produce those using the specified method you would need 20 nested for loops, not 26. I'm pretty sure you could give a separate name to each atom ont he known universe with a scheme like this. Do you really need 20-byte strings? regards Steve -- Steve Holden +44 150 684 7255 +1 800 494 3119 Holden Web LLC/Ltd http://www.holdenweb.com Skype: holdenweb http://del.icio.us/steve.holden Recent Ramblings http://holdenweb.blogspot.com -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
On Apr 13, 8:53 am, Steve Holden [EMAIL PROTECTED] wrote: Jia Lu wrote: for m in test: for n in test: for o in test: for p in test: print m+n+o+p Thanx for your anwser. But if I consider about a combination of over 26 letter's list just like: abcdefssdzxcvzxcvzcv asllxcvxcbbedfgdfgdg . Need I write 26 for loops to do this? Thanx Jia LU Your new example uses 20-byte strings anyway, so to produce those using the specified method you would need 20 nested for loops, not 26. I'm pretty sure you could give a separate name to each atom ont he known universe with a scheme like this. Do you really need 20-byte strings? regards Steve -- Steve Holden +44 150 684 7255 +1 800 494 3119 Holden Web LLC/Ltd http://www.holdenweb.com Skype: holdenwebhttp://del.icio.us/steve.holden Recent Ramblings http://holdenweb.blogspot.com- Hide quoted text - - Show quoted text - If you just expand the length to five million* or so, one of those strings will contain all the works of Shakespeare. -- Paul * ref: Project Gutenberg - http://www.gutenberg.org/etext/100 - unzipped plaintext is ~5.3Mb -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
If you just expand the length to five million* or so, one of those strings will contain all the works of Shakespeare. Oops, you have this formula in math? Actually I want to scan a range of network for some certain files. -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
On Apr 13, 9:27 am, Jia Lu [EMAIL PROTECTED] wrote: If you just expand the length to five million* or so, one of those strings will contain all the works of Shakespeare. Oops, you have this formula in math? Actually I want to scan a range of network for some certain files. Sorry, Jia Lu, I don't. I was actually just joking, alluding to the old saying that goes if you had an infinite number of monkeys typing randomly on an infinite number of typewriters, they will eventually type out the works of Shakespeare. Typewriters! who uses typewriters any more?! -- Paul -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
On Apr 13, 2007, at 9:19 AM, Paul McGuire wrote: If you just expand the length to five million* or so, one of those strings will contain all the works of Shakespeare. Not likely, even with a tiny sampling of the works of Shakespeare: # :-) import string import random def main(bardText, maxTries=500): tries = 0 while tries maxTries: tries += 1 attempt = [] for letter in bardText.lower(): if random.choice( string.lowercase[:26] + string.punctuation + ' ' ) == letter: attempt.append(letter) else: break if len(attempt) = 4: print '%d: %s' % ( tries, ''.join(attempt) ) if __name__ == __main__: main(Alas, poor Yorick!) -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
On Apr 13, 10:22 am, Michael Bentley [EMAIL PROTECTED] wrote: On Apr 13, 2007, at 9:19 AM, Paul McGuire wrote: If you just expand the length to five million* or so, one of those strings will contain all the works of Shakespeare. Not likely, even with a tiny sampling of the works of Shakespeare: # :-) import string import random def main(bardText, maxTries=500): tries = 0 while tries maxTries: tries += 1 attempt = [] for letter in bardText.lower(): if random.choice( string.lowercase[:26] + string.punctuation + ' ' ) == letter: attempt.append(letter) else: break if len(attempt) = 4: print '%d: %s' % ( tries, ''.join(attempt) ) if __name__ == __main__: main(Alas, poor Yorick!) 500 infinity Keep tryin'! Also, the OP's technique was not doing random string permutations, but generating an exhaustive list of all possible sequences from aaa... to zzz... . So I think the works of Shakespeare are *bound* to be in there somewhere. For proof, here's an extract from my sample code from running this exhaustive program with length=14: ... ALASPOORYORICG ALASPOORYORICH ALASPOORYORICI ALASPOORYORICJ ALASPOORYORICK ALASPOORYORICL ALASPOORYORICM ALASPOORYORICN ALASPOORYORICO ... -- Paul :) (too late for April 1, unfortunately) -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
On Fri, 2007-04-13 at 10:22 -0500, Michael Bentley wrote: On Apr 13, 2007, at 9:19 AM, Paul McGuire wrote: If you just expand the length to five million* or so, one of those strings will contain all the works of Shakespeare. Not likely, even with a tiny sampling of the works of Shakespeare: Actually, the OP seems to be interested in generating *all* strings of length N. If you generate the set of *all* strings of 5 million characters length, at least one of them will contain all works of Shakespeare. That statement is utterly true and utterly impractical, which is, of course, the point of Paul's joke. -Carsten -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
On Apr 13, 10:49 am, Carsten Haese [EMAIL PROTECTED] wrote: On Fri, 2007-04-13 at 10:22 -0500, Michael Bentley wrote: On Apr 13, 2007, at 9:19 AM, Paul McGuire wrote: If you just expand the length to five million* or so, one of those strings will contain all the works of Shakespeare. Not likely, even with a tiny sampling of the works of Shakespeare: Actually, the OP seems to be interested in generating *all* strings of length N. If you generate the set of *all* strings of 5 million characters length, at least one of them will contain all works of Shakespeare. That statement is utterly true and utterly impractical, which is, of course, the point of Paul's joke. -Carsten But even random typing will *eventually* get there (where eventually = several gazillion times the age of the universe) - see http://en.wikipedia.org/wiki/Infinite_monkey_theorem. -- Paul If I see farther, it is because I stand on the shoulders of an infinite number of monkeys. -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
On Apr 13, 8:53 am, Steve Holden [EMAIL PROTECTED] wrote: I'm pretty sure you could give a separate name to each atom ont he known universe with a scheme like this. Do you really need 20-byte strings? Steve, Based on the Wikipedia article's estimate of 10**79 atoms in the observable universe (is that all?), we would need a string of about 57 characters long to give each one a separate name. (And I'll bet you've typed on an old Royal or two in your time...) -- Paul -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
On Apr 13, 10:41 am, Paul McGuire [EMAIL PROTECTED] wrote: On Apr 13, 10:22 am, Michael Bentley [EMAIL PROTECTED] wrote: On Apr 13, 2007, at 9:19 AM, Paul McGuire wrote: If you just expand the length to five million* or so, one of those strings will contain all the works of Shakespeare. Not likely, even with a tiny sampling of the works of Shakespeare: # :-) import string import random def main(bardText, maxTries=500): tries = 0 while tries maxTries: tries += 1 attempt = [] for letter in bardText.lower(): if random.choice( string.lowercase[:26] + string.punctuation + ' ' ) == letter: attempt.append(letter) else: break if len(attempt) = 4: print '%d: %s' % ( tries, ''.join(attempt) ) if __name__ == __main__: main(Alas, poor Yorick!) 500 infinity Keep tryin'! Also, the OP's technique was not doing random string permutations, but generating an exhaustive list of all possible sequences from aaa... to zzz... . So I think the works of Shakespeare are *bound* to be in there somewhere. For proof, here's an extract from my sample code from running this exhaustive program with length=14: ... ALASPOORYORICG ALASPOORYORICH ALASPOORYORICI ALASPOORYORICJ ALASPOORYORICK ALASPOORYORICL ALASPOORYORICM ALASPOORYORICN ALASPOORYORICO ... -- Paul :) (too late for April 1, unfortunately)- Hide quoted text - - Show quoted text - And apologies to the OP for beating a dead horse into the ground. -- Paul -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
Paul McGuire wrote: On Apr 13, 8:53 am, Steve Holden [EMAIL PROTECTED] wrote: I'm pretty sure you could give a separate name to each atom ont he known universe with a scheme like this. Do you really need 20-byte strings? Steve, Based on the Wikipedia article's estimate of 10**79 atoms in the observable universe (is that all?), we would need a string of about 57 characters long to give each one a separate name. 10 ** 79 26 ** 20 True Well, we can't be right all the time, I suppose. Perhaps I need to raise my certainty filters. (And I'll bet you've typed on an old Royal or two in your time...) Who are you calling a monkey? look-out-for-my-infinite-number-of-friends-ly y'rs - steve -- Steve Holden +44 150 684 7255 +1 800 494 3119 Holden Web LLC/Ltd http://www.holdenweb.com Skype: holdenweb http://del.icio.us/steve.holden Recent Ramblings http://holdenweb.blogspot.com -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
Are you maybe trying to create a rainbow table, or a very big dictionary -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
Paul McGuire wrote: If I see farther, it is because I stand on the shoulders of an infinite number of monkeys. If I ever get around to writing a book on numerical methods/computational science/whatever, this will be the chapter quote for my chapter on Monte Carlo algorithms. -- Robert Kern I have come to believe that the whole world is an enigma, a harmless enigma that is made terrible by our own mad attempt to interpret it as though it had an underlying truth. -- Umberto Eco -- http://mail.python.org/mailman/listinfo/python-list
Problem with algorithm
Hi all. I want to create a large list like: ~ Is there any good algorithm to do this? Thanx Jia Lu -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
On Apr 12, 10:16�pm, Jia Lu [EMAIL PROTECTED] wrote: Hi all. �I want to create a large list like: ~ Is there any good algorithm to do this? Sure. test = '01' for m in test: for n in test: for o in test: for p in test: print m+n+o+p ## ##0001 ##0010 ##0011 ##0100 ##0101 ##0110 ##0111 ##1000 ##1001 ##1010 ##1011 ##1100 ##1101 ##1110 ## Now just change test='01' to test='abcdefghijklmnopqrstuvwxyz'. Thanx Jia Lu -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with algorithm
[EMAIL PROTECTED] wrote: On Apr 12, 10:16�pm, Jia Lu [EMAIL PROTECTED] wrote: Hi all. �I want to create a large list like: ~ Is there any good algorithm to do this? Sure. test = '01' for m in test: for n in test: for o in test: for p in test: print m+n+o+p [snip] Forgive any silly mistakes I have made (I've been teaching myself python for about 1 week) but there is a moderately well known algorithm for this that extends to arbitrary lengths of both the list of alternatives and the length of the required output, and avoids deeply nested loops. I know that it is no better for small and constant output lengths, but for longer lengths or if the output length can vary it should be better. There is a similar algorithm if duplicates are not allowed (ie abcd ... wxyz). My attempt at a python translation of the algorithm: def m_from_n ( v, m ): Print all combinations of m things from v[0] ... v[n-1], duplicates OK. Yields a list. x = [0] * m while True: yield [ v[i] for i in x ] i = m - 1 while i=0 and x[i]==len(v)-1: x[i] = 0 i = i - 1 if i = 0: x[i] = x[i] + 1 else: return for y in m_from_n( xyz, 2 ): print ''.join(y) xx xy xz yx yy yz zx zy zz for y in m_from_n( [0,1], 3 ): print y [0, 0, 0] [0, 0, 1] [0, 1, 0] [0, 1, 1] [1, 0, 0] [1, 0, 1] [1, 1, 0] [1, 1, 1] for y in m_from_n( abcdefghijklmnopqrstuvwxyz, 4 ): print ''.join(y) should more or less do what you want. Charles -- http://mail.python.org/mailman/listinfo/python-list
