Я пытаюсь реализовать Алгоритм O (ориентированные леса) от Дональда Э. Кнута: "Искусство компьютерного программирования - Том 4, Fascile 4, Генерация всех деревьев" на странице 24.
Мое решение Python:
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
Моя реализация дает мне:
[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].
Я уже слишком долго ищу ошибку. Надеюсь, кто-то может указать мне правильное направление исправления моего кода. Правильно ли я понимаю алгоритм? Любые улучшения в моем стиле Python также приветствуются. Спасибо за вашу помощь.