0

quick_find_union次のように（素朴な）を実装しようとしていました

class QF(object):
    def __init__(self,N):
        self.id=[x for x in range(N)]
    def connected(self,p,q):
        assert type(p)==int
        assert type(q)==int
        return self.id[p]==self.id[q]

    def union(self,p,q):
        assert type(p)==int
        assert type(q)==int
        for x in self.id:
            pid=self.id[p]
            qid=self.id[q]
            if x==pid:
                x=qid
#        for i in range(len(self.id)):
#            pid=self.id[p]
#            qid=self.id[q]
#            if self.id[i]==pid:
#                self.id[i]=qid

    def show_array(self):
        print self.id

if __name__=='__main__':
    qf=QF(10)
    qf.show_array()
    print qf.connected(1,4)
    qf.union(1,4)
    qf.show_array()
    print qf.connected(1,4)

これは戻ります

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
False
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
False

しかし、メソッドユニオンでコメントアウトされた部分のみを使用すると、期待どおりに機能します

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
False
[0, 4, 2, 3, 4, 5, 6, 7, 8, 9]
True

なぜこうなった？反復中に配列の要素を変更しようとすることと関係がありますか? 私はこれについてあまり明確ではありません..誰か説明してもらえますか?

4

1 に答える 1

0

x=qid名前が参照するxオブジェクトに名前を再バインドするだけです。リストqid内の要素は変更されません。self.id

を使用enumerate()してインデックスと値の両方を取得し、インデックスself.idを使用してリストを更新します。

for i, x in enumerate(self.id):
    pid=self.id[p]
    qid=self.id[q]
    if x==pid:
        self.id[i]=qid
于 2013-02-06T04:54:27.253 に答える