list – How to have a set of sets in Python?

>>> set([frozenset([1,2]), frozenset([2,3])])
set([frozenset([1, 2]), frozenset([2, 3])])

To represent a set of sets, the inner sets must be frozenset objects for the reason that the elements of a set must be hashable (all of Python’s immutable built-in objects are hashable). frozenset is immutable and set is mutable.

You cant have a set of sets in the usual sense but if you can work with frozenset objects then it can work:

>>> set([set([1,2]), set([3,4])])
Traceback (most recent call last):
  File <stdin>, line 1, in <module>
TypeError: unhashable type: set

This does work:

>>> set([frozenset([1,2]), frozenset([3,4])])
set([frozenset([1, 2]), frozenset([3, 4])])

list – How to have a set of sets in Python?

There is good reason why a set of sets does not work. Imagine the following (in pseudocode):

a = set(range(5))   # {0, 1, 2, 3, 4}
b = set(range(5, 10))  # {5, 6, 7, 8, 9}
c = set(range(5))  # {0, 1, 2, 3, 4}
# weve now created a set of sets, and then will drop `c` because its redundant
d = set([a, b, c])  # {{0, 1, 2... }, {5, 6, 7...}}
# now weve changed a value inside the set, suddenly everything changes
a.add(6)     # {{0, 1, 2..., 6}, {5, 6, 7...}}
# now we can re-add `c`
d.add(c)    # {{0, 1, 2..., 6}, {5, 6, 7...}, {0, 1, 2...}}

Besides the weird behavior of how elements would suddenly disappear, or act differently if they were mutable, there is also the lack of hash-based lookups.

The set implementation is very similar to the dict implementation, and can be found here. This is the implementation if a set contains a given key. Notice how it calculates the hash of the object, finds the first occurrence, and then does a lookup from the hash?

static int
set_contains_key(PySetObject *so, PyObject *key)
{
    long hash;
    setentry *entry;

    if (!PyString_CheckExact(key) ||
        (hash = ((PyStringObject *) key)->ob_shash) == -1) {
        hash = PyObject_Hash(key);
        if (hash == -1)
            return -1;
    }
    entry = (so->lookup)(so, key, hash);
    if (entry == NULL)
        return -1;
    key = entry->key;
    return key != NULL && key != dummy;
}

Now, if we modify a in the example above, how do we perform a lookup? The only solution would be item-by-item lookups, which would have O(n) time complexity.

Fortunately, there is an easy solution shown above: an immutable set. Fortunately, Python even has this builtin, the frozenset.

With a frozenset, since it is immutable, a hash can be calculated, both preventing unexpected behavior, but also restoring our O(1) lookups.

In this case, we can do the following:

a = frozenset(range(5))
b = frozenset(range(5, 10))
c = frozenset(range(5))
d = set([a, b, c])

And now, d will allow membership lookup on individual items, with solely discrete containers, since the frozenset members are immutable.

list – How to have a set of sets in Python?

list – How to have a set of sets in Python?

Leave a Reply Cancel reply