You can always substitute Iteration for Recursion by making the stack an
explicit part of your code. As an example, imagine you are traversing this
directory tree:
birds
birds/owls
birds/owls/snowy
birds/owls/barn
birds/owls/great-horned
birds/eagles
birds/eagles/golden
birds/eagles/bald
birds/eagles/osprey
Where the third-level items are files, rather than more directories.
In a recursive approach, a function is defined that does the recursion. This is
a feature of recursion. You can't slip it inline with your code (unless your
language supports inline functions and the right sort of scoping rules, but
you probably don't want to try that here). The function takes a directory,
iterates through the contents, calling itself again for every subdirectory.
Your application code calls the function with the argument of "birds". The
function then calls itself twice, once with "owls" and again with "eagles".
The contents of these are files, and not directories, so recursion ends.
In an iterative approach, there is a stack and a loop. The loop stops when the
stack is empty. The loop pops the most recently pushed item from the stack,
and then pushes onto the stack any subdirectories.
We start with the directory "birds" on the stack. The loop pops "birds" and
then pushes "owls" and "eagles". It loops twice more to process these, and
then stops.
Your program is really more iterative than recursive. I couldn't manage a
recursive expression of the problem. You can always make a iterative version
of a recursive algorithm, but not necessarily the other way. This makes sense
when you inspect the problem. Your solution is abstractly equivalent to an n-
dimensional "cube" with side length equal to the length of the alphabet, not
anything that looks like a tree. One thing I noticed about your generated code
is that it can be collapsed into a list comprehension:
>>> allwrds('ab',2)
listOfWords=[]
for l0 in alphabet:
for l1 in alphabet:
word = "".join([eval("l"+str(i)) for i in range(n)])
listOfWords.append(word)
['aa', 'ab', 'ba', 'bb']
is equivalent to
>>> alphabet='ab'
>>> [l0+l1 for l0 in alphabet for l1 in alphabet]
['aa', 'ab', 'ba', 'bb']
Now, the result is a 1D list of length len(alphabet)**n. Why not iterate over
that space, and fill in the blanks? Think of your problem modeled as a n-
dimensional hypercube. The value at any element is equal to the concatenation
of the n indices of that element's location. Some 2D examples:
allwrds('ab',2):
a b
a aa ab
b ba bb
allwrds('abc',2):
a b c
a aa ab ac
b ba bb bc
c ca cb cc
Mapping from n dimensions to 1D isn't hard if you know the size of each
dimension. In this case, they're all equal. I'll use a 3D example to make it
more clear:
i = 0
j=0 1 2
k
0 0 1 2
1 3 4 5
2 6 7 8
i = 1
j=0 1 2
k
0 9 10 11
1 12 13 14
2 15 16 17
i = 2
j=0 1 2
k
0 18 19 20
1 21 22 23
2 24 25 26
Find the i,j,k for 1D index 17.
Start with the highest order index (i). Divide by the product of the sizes of
the lower dimensions, which is the length of the alphabet squared. This
alphabet is length 3, so we divide by 9. We get 1 rmdr 8. i=1. Now take the
remainder and repeat. 8 divided by 3 is 2 rmdr 2. j=2. You could take it
another step if using n-cubes and powers of the dimension size, since 3**0
equals one, and the next answer is still 2, but this fails when the dimensions
aren't all equal. k=2. Got that?
Now these i,j,k values are just indices into the alphabet! Just get the letter
at that indexd and join them up. Here's the code:
def allwrds(alphabet, n):
listOfWords=[]
for i in range(len(alphabet)**n):
word = ''
q = i
for j in range(n-1):
q, r = divmod(q, len(alphabet))
word += alphabet[q]
q = r
word += alphabet[q]
listOfWords.append(word)
return listOfWords
Cheers
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
