Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Problem with algorithm

Reply
Thread Tools

Problem with algorithm

 
 
Jia Lu
Guest
Posts: n/a
 
      04-13-2007
Hi all.
I want to create a large list like:

aaaa ~ zzzz

Is there any good algorithm to do this?

Thanx

Jia Lu

 
Reply With Quote
 
 
 
 
mensanator@aol.com
Guest
Posts: n/a
 
      04-13-2007
On Apr 12, 10:16�pm, "Jia Lu" <(E-Mail Removed)> 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



 
Reply With Quote
 
 
 
 
Charles Sanders
Guest
Posts: n/a
 
      04-13-2007
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> On Apr 12, 10:16�pm, "Jia Lu" <(E-Mail Removed)> 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[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
 
Reply With Quote
 
Paul Rubin
Guest
Posts: n/a
 
      04-13-2007
Charles Sanders <(E-Mail Removed)> 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))
 
Reply With Quote
 
Charles Sanders
Guest
Posts: n/a
 
      04-13-2007
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
 
Reply With Quote
 
Jia Lu
Guest
Posts: n/a
 
      04-13-2007

> 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

 
Reply With Quote
 
azrael
Guest
Posts: n/a
 
      04-13-2007
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" <(E-Mail Removed)> 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



 
Reply With Quote
 
Paddy
Guest
Posts: n/a
 
      04-13-2007
On Apr 13, 8:16 am, "Jia Lu" <(E-Mail Removed)> 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/Coo.../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.

 
Reply With Quote
 
Michael Hoffman
Guest
Posts: n/a
 
      04-13-2007
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
 
Reply With Quote
 
azrael
Guest
Posts: n/a
 
      04-13-2007
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 <(E-Mail Removed)> 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



 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Filtered Back Projection Algorithm (FBP Algorithm) Bapaiah Katepalli VHDL 1 06-23-2006 04:50 PM
Re: Recursion problem - Graph theory - Algorithm needed Allan W C++ 4 01-22-2004 02:42 PM
Recursion problem - Graph theory - Algorithm needed JimC C++ 3 01-17-2004 12:43 PM
Key generation algorithm and Cipher algorithm Ahmed Moustafa Java 0 11-15-2003 06:35 AM
algorithm problem Adam VHDL 5 11-08-2003 06:26 PM



Advertisments