TAoCP Oriented Forest - Algorithm in python
I'm trying to implement Algorithm O (Oriented Scaffolding) from Donald Knuth: "The Art of Computer Programming - Volume 4, Fascile 4" Generating All Trees "on page 24.
My Python solution:
def generate_oriented_forest(n):
"""Algorithm O from Knuth TAoCP, Fascicle 4, p. 25. """
p = range(-1, n)
while True:
yield p[1:]
if p[n] > 0: p[n] = p[p[n]]
else:
k_largest = 0
for k in range(1,n):
if p[k] != 0: k_largest = k
k = k_largest
if k == 0: return
j = p[k]
d = k-j
if p[k-d] == p[j]: p[k] = p[j]
else: p[k] = p[k-d] + d
while k != n:
#print k, p
k = k+1
if p[k-d] == p[j]: p[k] = p[j]
else: p[k] = p[k-d] + d
if __name__ == "__main__":
for el in generate_oriented_forest(4):
print el
# According to page 23 and also Table 1 p.4 I would expect the sequence:
# 0123, 0122, 0121, 0120, 0111, 0110, 0101, 0100, 0000
My implementation gives me:
[0, 1, 2, 3], [0, 1, 2, 2], [0, 1, 2, 1], [0, 1, 2, 0], [0, 1, 1, 1], [0, 1, 1, 0],
[0, 1, 0, 3] ,
[0, 1, 0, 0], [0, 0, 0, 0].
I've been looking for the error for too long. Hopefully someone can point me in the right direction to fix my code. Am I understanding the algorithm correctly? Any improvements to my python style are also welcome. Thanks for your help.
source to share
Congratulations!
It looks like you just found a bug in TAOCP. As you undoubtedly know, there is a one-dollar hex reward (drawn on the San Serife Bank) for the first seeker of such errors. I have one, and I can tell you, it's the hell to put on your wall.
It seems to me that "+ d" in step O5 is wrong; at least I can't find a way to match it up with the cloning step description in the text description before the algorithm. I've checked the most recent fixes for V4f4 and it's not there, so you seem to be the first to notice it.
To be sure, I recommend that you calculate the values for n = 5 with and without "+ d" and see which ones match the expected results. If it goes as I suspect, please write it and email it to Knut (the address for TAOCP errors is on his website) along with your mailing address and you should receive a response (by paper mail) within 6 months.
source to share
I've tweaked your code a bit, mostly to eliminate duplication in step 5.
However, the output is still the same as you get
def generate_oriented_forest(n):
"""Algorithm O from Knuth TAoCP, Fascicle 4, p. 25. """
p = range(-1,n)
while True:
yield p[1:]
if p[n] > 0:
p[n] = p[p[n]]
continue
for k in range(n-1,0,-1):
if p[k] != 0: break
else:
break
j = p[k]
d = k-j
while True:
if p[k-d] == p[j]:
p[k] = p[j]
else:
p[k] = p[k-d] + d
if k==n:
break
k+=1
if __name__ == "__main__":
for el in generate_oriented_forest(4):
print el
source to share
I don't understand the algorithm and have no idea if my suggested algorithm change (below) is correct or not. All I know is that it produces the expected output that you specify for n = 4:
def generate_oriented_forest(n):
"""Algorithm O from Knuth TAoCP, Fascicle 4, p. 25. """
p = range(-1,n)
while True:
yield p[1:]
if p[n] > 0:
p[n] = p[p[n]]
continue
for k in range(n-1,0,-1):
if p[k] != 0: break
else:
break
j = p[k]
d = k-j
while True:
if p[k-d] == p[j]:
p[k] = p[j]
else:
p[k] = p[k-d]
if k==n:
break
k+=1
I used the gnibbler code as a starting point. I used traceit () and dumped instructions to execute the code as it went from [0, 1, 1, 0] → [0, 1, 0, 3].
I find this is the state of the variables:
[0, 1, 1, 0] # the last yield
k: 4
d: 2
j: 1
p: [-1, 0, 1, 0, 0]
[0, 1, 0, 3] # the problem yield
and this is the only time this code is executed:
__main__:19: if p[k-d] == p[j]:
__main__:22: p[k] = p[k-d] + d
Since p [kd] = p [2] = 1 and you want p [k] to equal 1, I assume that the correct formula should be p [k] = p [k-d].
I also changed
for k in range(n-1,-1,-1):
to
for k in range(n-1,0,-1):
to stop the code from getting an extra [0, 0, 0, 0] at the end.
source to share
I dug up the original article: SIAM Journal of Computing, T. Beyer and SM Hedetniemi, "Conquering the Permanent Root of Trees". The article explains the algorithm very well. Here's my implementation:
def generate_oriented_forest_2(n):
"""SIAM J. COMPUT. Vol. 9, No. 4, November 1980
T. Beyer and S.M. Hedetniemi: constant time generation of rooted trees."""
L = range(-1, n)
while True:
yield L[1:]
if L[n] > 0: L[n] = L[L[n]]
else:
for p in range(n-1, 0, -1):
if L[p] != 0: break
else: break
for q in range(p-1, 0, -1):
if L[q] == L[p] - 1: break
i = p
while i <= n:
L[i] = L[i-(p-q)]
i += 1
This gives me the expected result. But I'm still wondering why Knuth's algorithm isn't working. It would be great to know.
source to share
Answer: everyone is right!
Knuth's algorithm calculates parent codes, not level codes. It seems that "Donald" was still thinking in terms of parent codes, even noting that Algorithm B and H uses level codes instead.
However, if you look at the text of Algorithm O, you should notice that Knuth mentions that "each canonical forest is represented directly by its sequence of parent pointers p 1 ... pn, assuming nodes."
So, this algorithm should use parent codes, not level codes. This Knut, he's tricky ... So, I frankly copied the unutbu code to come up with a level code-generating version that looks more like what you wrote:
def generate_oriented_forest(n):
"""Algorithm O from Knuth TAoCP, Fascicle 4, p. 25. """
p = range(-1,n)
while True:
yield p[1:]
if p[n] > 0:
p[n] = p[p[n]]
continue
for k in range(n-1,0,-1):
if p[k] != 0: break
else:
break
j = p[k]
for q in range(1,k):
if p[k-q] == p[j]: break
while True:
p[k] = p[k-q]
if k==n:
break
k+=1
if __name__ == "__main__":
for el in generate_oriented_forest(4):
print el
Hope this answered your question. :)
source to share