How to maintain a set of sets?

Question

I've seen the related question, but I can't use a frozenset for my inner-sets. I want everything to be mutable.

As I understand it, Python gives everything an ID, so why can't it use that as its hash? I need to maintain a list of references to all the inner-sets, even as they change.

Edit: Ok, I understand why, but in this case it would be preferable, as I only care about reference equality, not value equality.

How can I do this?

You're going to ask "why", so I'll give you some code:

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

I've essentially got a game board, and I want to divide the pieces on the board into groups (or "chains"). The above code works fine until I added all_chains -- it creates all the sets, but then I have no way of accessing each the sets its created without iterating over the whole board again.

So how do I maintain a list of all the sets it's created? Keep in mind that I need to remove sets too (which is why I want to use another set for the outter set).

Wrapping the reference in weakref.ref() didn't work either:

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

Assuming you already understand _why_ mutable objects aren't hashable, you could subclass `set()` and create a `__hash__()` method which returns it's `id`. That should allow you to make sets of sets. Another option is to make hashable representations of your inner sets, also using these representations as keys mapping them to the actual objects. — Joel Cornett, Jul 14 '12 at 02:13
The reason the id of a set doesn't make a sensible hash for it is that 2 sets containing the same values won't have the same hash. — Wooble, Jul 14 '12 at 02:13
@Wooble has it: the problem here is that, if you were to use a set's ID as its hash, you wouldn't actually have a set-of-sets. You'd have a bag-of-sets, since you could insert two identical inner sets into the outer container. — Borealid, Jul 14 '12 at 02:16
@Wooble: Yeah, okay, I understand that, but in this specific case I actually care about the references, not the values. — mpen, Jul 14 '12 at 02:19
@Mark if you only care about the references, maybe you should use a dictionary of sets, where k = id(set) and v = set. — Adam Wagner, Jul 14 '12 at 02:20
@AdamWagner: Precisely what I ended up doing. Except I used my own GUID. — mpen, Jul 14 '12 at 02:24

mpen · Answer 1 · 2012-07-14T02:32:55.843

Decided to use a dictionary of sets instead.

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)

It's not quite as pretty because I always have to look up the set in the dictionary before I can use it, but it seems to work.

Input:

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

Output:

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)])}

@JoelCornett: Yes. Right in the middle there I delete sets as well (when I merge two together). If I had used a list, all the indices would be shuffled over, and that would mess up all my "references". — mpen, Jul 14 '12 at 02:35

How to maintain a set of sets?

1 Answers1