Problem with algorithm

[Jia Lu]

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

aaaa ~ zzzz

Is there any good algorithm to do this?

Thanx

Jia Lu

[mensanator@aol.com]

Re: Problem with algorithm

On Apr 12, 10:16�pm, "Jia Lu" <Roka...@gmail. comwrote:

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='abcdefghi jklmnopqrstuvwx yz'.

>
Thanx
>
Jia Lu

[Charles Sanders]

Re: Problem with algorithm

mensanator@aol. com wrote:

On Apr 12, 10:16�pm, "Jia Lu" <Roka...@gmail. comwrote:

>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[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( "abcdefghijklmn opqrstuvwxyz", 4 ):
print ''.join(y)

should more or less do what you want.

Charles

[Paul Rubin]

Re: Problem with algorithm

Charles Sanders <C.delete_this. Sanders@BoM.GOv .AUwrites:

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))

[Charles Sanders]

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

[Jia Lu]

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:
"abcdefssdzxcvz xcvzcv"
"asllxcvxcbbedf gdfgdg"
......

Need I write 26 for loops to do this?

Thanx

Jia LU

[azrael]

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
getrecoursionli mit() and setrecoursionli mit().



On Apr 13, 9:16 am, "Jia Lu" <Roka...@gmail. comwrote:

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:
"abcdefssdzxcvz xcvzcv"
"asllxcvxcbbedf gdfgdg"
.....
>
Need I write 26 for loops to do this?
>
Thanx
>
Jia LU

[Paddy]

Re: Problem with algorithm

On Apr 13, 8:16 am, "Jia Lu" <Roka...@gmail. comwrote:

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:
"abcdefssdzxcvz xcvzcv"
"asllxcvxcbbedf gdfgdg"
.....
>
Need I write 26 for loops to do this?
>
Thanx
>
Jia LU

Try this: http://aspn.activestate.com/ASPN/Coo.../Recipe/502199

You could then write something like:

import string
for thiscomb in comb2( *([string.lowercas e]*26) ):
...

Mind you, it generates a lot of combinations.

- Paddy.

[Michael Hoffman]

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
getrecoursionli mit() and setrecoursionli mit().

Well, you'd have to spell sys.getrecursio nlimit() 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]

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 multidimensiona l hash.

Best Regards


On Apr 13, 2:24 pm, Michael Hoffman <cam.ac...@mh39 1.invalidwrote:

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
getrecoursionli mit() and setrecoursionli mit().

>
Well, you'd have to spell sys.getrecursio nlimit() 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

[Steve Holden]

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:
"abcdefssdzxcvz xcvzcv"
"asllxcvxcbbedf gdfgdg"
.....
>
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

[Paul McGuire]

Re: Problem with algorithm

On Apr 13, 8:53 am, Steve Holden <s...@holdenweb .comwrote:

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:
"abcdefssdzxcvz xcvzcv"
"asllxcvxcbbedf gdfgdg"
.....

>

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

[Jia Lu]

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.

[Paul McGuire]

Re: Problem with algorithm

On Apr 13, 9:27 am, "Jia Lu" <Roka...@gmail. comwrote:

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." "Typewriter s"! who uses
typewriters any more?!

-- Paul

[Michael Bentley]

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=500000 0):
tries = 0
while tries < maxTries:
tries += 1
attempt = []
for letter in bardText.lower( ):
if random.choice(
string.lowercas e[:26]
+ string.punctuat ion
+ ' '
) == letter:
attempt.append( letter)
else:
break
if len(attempt) >= 4:
print '%d: %s' % (
tries,
''.join(attempt )
)

if __name__ == "__main__":
main("Alas, poor Yorick!")