Ориентированный лесной TAoCP - алгоритм в питоне - PullRequest
Новая
       46

Ориентированный лесной TAoCP - алгоритм в питоне

2 голосов
/ 28 октября 2009

Я пытаюсь реализовать Алгоритм 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 также приветствуются. Спасибо за вашу помощь.

Ответы [ 5 ]

2 голосов
/ 11 ноября 2009

Поздравляем!

Похоже, вы только что нашли ошибку в TAOCP. Как вы, несомненно, знаете, за первое обнаружение таких ошибок вознаграждается один шестнадцатеричный доллар (выписанный на Банке Сан-Серифе). У меня есть один, и я могу сказать вам, это адская вещь, чтобы положить на вашу стену.

Мне, конечно, кажется, что " + d " на шаге O5 ошибочно; по крайней мере, я не могу найти способ согласовать его с описанием шага «клонирования» в текстовом описании перед алгоритмом. Я проверил последние исправления для V4f4, а этого там нет, так что, похоже, вы первый заметили это.

Чтобы проверить, я рекомендую вам рассчитать значения для n = 5 как с " + d ", так и без него, и посмотреть, какие из них соответствуют ожидаемым результатам. Если это произойдет так, как я подозреваю, напишите его и отправьте Кнуту по электронной почте (адрес для ошибок TAOCP есть на его веб-сайте) вместе с вашим почтовым адресом, и вы должны получить ответ (по почте) в течение 6 месяцев. .

0 голосов
/ 17 марта 2011

Ответ таков: все правы!

Алгоритм Кнута вычисляет родительские коды, а не коды уровней. Кажется, что «Дональд» все еще думал с точки зрения родительских кодов, даже отмечая, что алгоритм B & H вместо этого использует коды уровня.

Однако, если вы посмотрите на текст алгоритма O, вы должны заметить, что Кнут упоминает, что «каждый канонический лес представлен непосредственно своей последовательностью родительских указателей p 1 ... p n в предзаказе узлов. "

Итак, этот алгоритм должен использовать родительские коды, а не коды уровней. Этот Кнут, он лукавый ... Итак, я явно скопировал код unutbu, чтобы создать версию, генерирующую код уровня, которая больше похожа на то, что вы написали: 

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

Надеюсь, это ответило на ваш вопрос. :)

0 голосов
/ 28 октября 2009

Я не понимаю алгоритм и понятия не имею, является ли мое предлагаемое изменение алгоритма (ниже) правильным или нет. Все, что я знаю, это то, что он выдает ожидаемый результат, который вы цитируете для 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

Я использовал код Гнибблера в качестве отправной точки. Я использовал traceit () и операторы печати, чтобы следовать коду при его переходе от [0, 1, 1, 0] -> [0, 1, 0, 3].

Я обнаружил, что это состояние переменных: 

[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

и это единственный раз, когда выполняется этот код: 

__main__:19:             if p[k-d] == p[j]:
__main__:22:                 p[k] = p[k-d] + d

Поскольку p [k-d] = p [2] = 1, и вы хотите, чтобы p [k] равнялось 1, я «думаю», правильная формула должна быть р [к] = р [к-d].

Я тоже изменился 

for k in range(n-1,-1,-1):

до 

for k in range(n-1,0,-1):

чтобы код не выдал дополнительный [0, 0, 0, 0] в конце.

0 голосов
/ 30 октября 2009

Я выкопал оригинальную статью: SIAM Journal of Computing, T. Beyer и S.M. Хедетниеми, «Генерация корневых деревьев с постоянным временем». В статье очень хорошо объясняется алгоритм. Вот моя реализация: 

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

Это дает мне ожидаемый результат. Но мне все еще интересно, почему алгоритм Кнута не работает. Было бы здорово узнать.

0 голосов
/ 28 октября 2009

Я немного реорганизовал ваш код, в основном для устранения дублирования на шаге 5.
Однако результат остается таким же, как вы получаете 

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