Problem with algorithm

Discussion in 'Python' started by Jia Lu, Apr 13, 2007.

  1. Jia Lu

    Jia Lu Guest

    Hi all.
    I want to create a large list like:

    aaaa ~ zzzz

    Is there any good algorithm to do this?

    Thanx

    Jia Lu
    Jia Lu, Apr 13, 2007
    #1
    1. Advertising

  2. Jia Lu

    Guest

    On Apr 12, 10:16�pm, "Jia Lu" <> wrote:
    > Hi all.
    >  I want to create a large list like:
    >
    > aaaa ~ zzzz
    >
    > 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


    ## 0000
    ## 0001
    ## 0010
    ## 0011
    ## 0100
    ## 0101
    ## 0110
    ## 0111
    ## 1000
    ## 1001
    ## 1010
    ## 1011
    ## 1100
    ## 1101
    ## 1110
    ## 1111

    Now just change test='01' to test='abcdefghijklmnopqrstuvwxyz'.


    >
    > Thanx
    >
    > Jia Lu
    , Apr 13, 2007
    #2
    1. Advertising

  3. wrote:
    > On Apr 12, 10:16�pm, "Jia Lu" <> wrote:
    >> Hi all.
    >> �I want to create a large list like:
    >>
    >> aaaa ~ zzzz
    >>
    >> 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 for i in x ]
    i = m - 1
    while i>=0 and x==len(v)-1:
    x = 0
    i = i - 1
    if i >= 0:
    x = x + 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
    Charles Sanders, Apr 13, 2007
    #3
  4. Jia Lu

    Paul Rubin Guest

    Charles Sanders <> 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))
    Paul Rubin, Apr 13, 2007
    #4
  5. 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
    Charles Sanders, Apr 13, 2007
    #5
  6. Jia Lu

    Jia Lu Guest


    > 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
    Jia Lu, Apr 13, 2007
    #6
  7. Jia Lu

    azrael Guest

    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" <> 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
    azrael, Apr 13, 2007
    #7
  8. Jia Lu

    Paddy Guest

    On Apr 13, 8:16 am, "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

    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.
    Paddy, Apr 13, 2007
    #8
  9. 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
    Michael Hoffman, Apr 13, 2007
    #9
  10. Jia Lu

    azrael Guest

    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 <> 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
    azrael, Apr 13, 2007
    #10
  11. Jia Lu

    Steve Holden Guest

    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
    Steve Holden, Apr 13, 2007
    #11
  12. Jia Lu

    Paul McGuire Guest

    On Apr 13, 8:53 am, Steve Holden <> 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: holdenweb http://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
    Paul McGuire, Apr 13, 2007
    #12
  13. Jia Lu

    Jia Lu Guest


    > 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.
    Jia Lu, Apr 13, 2007
    #13
  14. Jia Lu

    Paul McGuire Guest

    On Apr 13, 9:27 am, "Jia Lu" <> 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
    Paul McGuire, Apr 13, 2007
    #14
  15. 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=5000000):
    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!")
    Michael Bentley, Apr 13, 2007
    #15
  16. Jia Lu

    Paul McGuire Guest

    On Apr 13, 10:22 am, 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:
    >
    > # :)
    >
    > import string
    > import random
    >
    > def main(bardText, maxTries=5000000):
    > 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!")


    5000000 << 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)
    Paul McGuire, Apr 13, 2007
    #16
  17. 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
    Carsten Haese, Apr 13, 2007
    #17
  18. Jia Lu

    Paul McGuire Guest

    On Apr 13, 10:49 am, Carsten Haese <> 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.
    Paul McGuire, Apr 13, 2007
    #18
  19. Jia Lu

    Paul McGuire Guest

    On Apr 13, 8:53 am, Steve Holden <> 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
    Paul McGuire, Apr 13, 2007
    #19
  20. Jia Lu

    Paul McGuire Guest

    On Apr 13, 10:41 am, "Paul McGuire" <> wrote:
    > On Apr 13, 10:22 am, 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:

    >
    > > # :)

    >
    > > import string
    > > import random

    >
    > > def main(bardText, maxTries=5000000):
    > > 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!")

    >
    > 5000000 << 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
    Paul McGuire, Apr 13, 2007
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Adam

    algorithm problem

    Adam, Nov 3, 2003, in forum: VHDL
    Replies:
    5
    Views:
    3,122
    A123b456c
    Nov 8, 2003
  2. Ahmed Moustafa
    Replies:
    0
    Views:
    764
    Ahmed Moustafa
    Nov 15, 2003
  3. JimC
    Replies:
    3
    Views:
    509
  4. Allan W
    Replies:
    4
    Views:
    518
    Jos A. Horsmeier
    Jan 22, 2004
  5. Bapaiah Katepalli
    Replies:
    1
    Views:
    1,481
    Mike Treseler
    Jun 23, 2006
Loading...

Share This Page