如何维护一组集合？

Question

如何维护一组集合？

3

我看到了相关问题，但是我不能使用frozenset作为我的内部集合。我希望一切都是可变的。

据我所知，Python会给每个对象分配一个ID，那么为什么不能将其用作哈希值呢？我需要维护对所有内部集合的引用列表，即使它们发生改变。 编辑：好的，我明白了为什么，但在这种情况下，这是更可取的，因为我只关心引用相等性，而不是值相等性。

我该怎么做？

你可能会问“为什么”，所以我给你一些代码：

def remove_captured(self):
    all_chains = set()
    chains = Grid(self.rows, self.cols)
    for m, n, stone in self.enumerate():
        if stone == self[m - 1, n]:
            chains[m, n] = chains[m - 1, n]
            if stone == self[m, n - 1]:
                all_chains.discard(chains[m, n - 1])
                chains[m, n].update(chains[m, n - 1])
                for s in chains[m, n - 1]:
                    chains[s] = chains[m, n]
        elif stone == self[m, n - 1]:
            chains[m, n] = chains[m, n - 1]
        else:
            chains[m, n] = set()
            all_chains.add(chains[m, n])
        chains[m, n].add((m,n))
    chains._print()
    print all_chains

我基本上有一个游戏板，我想将棋子分成组（或“链”）。上面的代码很好用，直到我添加了all_chains - 它创建了所有集合，但是我没有办法访问它创建的每个集合，而不必再次遍历整个棋盘。

那么我如何维护它创建的所有集合的列表？请记住，我还需要删除集合（这就是为什么我想使用另一个集合作为外部集合的原因）。

将引用包裹在weakref.ref()中也不起作用：

all_chains.add(weakref.ref(chains[m, n])) # TypeError: unhashable type: 'set'

- mpen

假设您已经理解了可变对象为什么不是可哈希的原因，您可以子类化 set() 并创建一个 __hash__() 方法，该方法返回其 id。这应该允许您创建集合的集合。另一个选项是创建内部集合的可哈希表示，同样使用这些表示作为键将它们映射到实际对象。 - Joel Cornett

6

集合的id作为哈希值并不可行的原因是，包含相同元素的两个集合将不会有相同的哈希值。 - Wooble

1

@Wooble已经指出了问题所在：如果您将一个集合的ID用作其哈希值，那么您实际上并没有一个集合的集合。您会得到一个集合的袋子，因为您可以将两个相同的内部集合插入到外部容器中。 - Borealid

@Wooble：是的，好的，我理解了，但在这种特定情况下，我实际上关心的是引用，而不是值。 - mpen

3

如果您只关心参考文献，也许您应该使用一本集合字典，其中 k = id(set)，v = set。 - Adam Wagner

@AdamWagner：我最终做的就是这样。只不过我使用了自己的GUID。 - mpen

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mpen · Accepted Answer

决定使用一个集合字典。

def remove_captured(self):
    cdict = {}
    cid = 0
    chains = Grid(self.rows, self.cols)
    for m, n, stone in self.enumerate():
        if stone == self[m - 1, n]:
            chains[m, n] = chains[m - 1, n]
            if stone == self[m, n - 1] and chains[m, n] != chains[m, n - 1]:
                del_id = chains[m, n - 1]
                cdict[chains[m, n]].update(cdict[del_id])
                for c in cdict[del_id]:
                    chains[c] = chains[m, n]
                del cdict[del_id]
        elif stone == self[m, n - 1]:
            chains[m, n] = chains[m, n - 1]
        else:
            cdict[cid] = set()
            chains[m, n] = cid
            cid += 1
        cdict[chains[m, n]].add((m, n))
    chains._print()
    pprint(cdict)

这个设置不太好看，因为我总是需要在使用之前查字典，但它似乎能够正常工作。

输入：

0  .  W  W  W  W
1  W  B  B  B  .
2  .  .  .  W  .
3  .  B  B  W  W
4  .  .  B  W  .
   0  1  2  3  4

输出：

0 0 1 1 1 1
1 2 3 3 3 4
2 5 5 5 6 4
3 5 7 7 6 6
4 5 5 7 6 8
  0 1 2 3 4
{0: set([(0, 0)]),
 1: set([(0, 1), (0, 2), (0, 3), (0, 4)]),
 2: set([(1, 0)]),
 3: set([(1, 1), (1, 2), (1, 3)]),
 4: set([(1, 4), (2, 4)]),
 5: set([(2, 0), (2, 1), (2, 2), (3, 0), (4, 0), (4, 1)]),
 6: set([(2, 3), (3, 3), (3, 4), (4, 3)]),
 7: set([(3, 1), (3, 2), (4, 2)]),
 8: set([(4, 4)])}