Реализация Union-Find, получение TypeError: объект builtin_function_or_method не является подпиской - PullRequest
Новая
       14

Реализация Union-Find, получение TypeError: объект builtin_function_or_method не является подпиской

0 голосов
/ 06 июля 2019

Я пытаюсь реализовать быстрое объединение с алгоритмом сжатия пути, и по какой-то причине я получаю TypeError: 'builtin_function_or_method' object is not subscriptable при тестировании. Все это выглядит хорошо для меня. Вот код; Я ценю вашу помощь.

Вот полная ошибка, за которой следует код: 

Traceback (most recent call last):
  File "quick-find.py", line 75, in <module>
    a.union(7,9)
  File "quick-find.py", line 56, in union
    node2_root = self.root(node2)
  File "quick-find.py", line 47, in root
    self.id[node] = self.id[id[node]]
TypeError: 'builtin_function_or_method' object is not subscriptable

class weightedQuickUnion:
    def __init__(self, n):
        self.id = list(range(n))
        self.size = list([1]) * n

    def root( self, node ):
        # Improved to make every node point to its parent
            # This improvement makes it weightedQuickUnionWithPathCompression
        while ( node != self.id[node]):
            self.id[node] = self.id[id[node]]
            node = self.id[node]
        return node

    def connected(self, node1, node2):
        return self.id[node1] == self.id[node2]

    def union(self, node1, node2):
        node1_root = self.root(node1)
        node2_root = self.root(node2)
        if node1_root == node2_root:
            return
        if (self.size[node1_root] < self.size[node2_root]):
            self.id[node1_root] = node2_root
            self.size[node2_root] += self.size[node1_root]
        else:
            self.id[node2_root] = node1_root
            self.size[node1_root] += self.size[node2_root]

a = weightedQuickUnion(10)
print(a.id)
print(a.size)
print(a.connected(3,4))
a.union(3,4)
a.union(1,3)
a.union(6,9) 
print(a.id)
print(a.size)
a.union(7,9) # <-- this line throws an exception and I can't figure out why.
a.union(8,9)

1 Ответ

0 голосов
/ 06 июля 2019

Спасибо @jasonharper за указание, что я отбросил "я".из следующей строки: 

self.id[node] = self.id[id[node]]

Вместо этого должно быть: 

self.id[node] = self.id[self.id[node]]
...