Python Enum Flags and Basic Set Theory#

Date: 2022-Jun-23

Python’s enum module does a bunch of nifty tricks to make enumerations. One of its coolest features, though, at least in my opinion, is the Flag enum type. For example, you can use it to represent Unix octal permissions:

>>> class Permission(Flag):
...     READ = 0b100
...     WRITE = 0b010
...     EXECUTE = 0b001

>>> Permission.READ | Permission.WRITE | Permission.EXECUTE
<Permission.READ|WRITE|EXECUTE: 7>

Or, using the Python documentation’s own example, you can represent a 3-bit color:

>>> class Color(Flag):
...     RED = auto()
...     BLUE = auto()
...     GREEN = auto()
...     WHITE = RED | BLUE | GREEN
...
>>> Color.WHITE
<Color.WHITE: 7>

However, all of these have a deeper connection: to set theory.

Basic Set Theory#

Let’s get some introductories out of the way first. If you know all this, skip to Python Sets.

Please know that I am not a mathematician and may get some things wrong here. Just accept me as incompetent and move on.

Definitions#

  • A set is a collection of unique objects. For example, \(\{A, B, C\}\), \(\{420, Earth\}\), and \(\{\{12\}, \{20, 21\}\}\) are all sets.

    • Besides by listing their members, sets can also be defined by an unambiguous characteristic of their members: \(\{x : x \geq A \land x \leq C\}\) is another way to define the first set above, assuming letters can be compared like that.

  • An object is a member of a set if the set contains the object. For example, if \(S = \{A, B, C\}\), \(A \in S\) (A is in S) but \(D \notin S\) (D is not in S).

  • There are two special sets:

    • The empty set, \(\emptyset\), which contains no objects (no object is a member of the empty set).

    • The universe set, denoted here as \(U\), which contains all objects (if an object is a member of any set, it is a member of the universe set).

Operations#

The following examples use the sets \(A = \{1, 2, 3\}\) and \(B = \{2, 3, 4\}\), and the universe \(U = \{1, 2, 3, 4, 5\}\). Note that all characteristic-based set definitions here assume the implicit additional criterion that \(x \in U\).

  • The union of two sets is a set such that if an object is a member of either set, it is also a member of their union. That is, \(A \cup B = \{x : x \in A \lor x \in B\}\). For example, \(A \cup B = \{1, 2, 3, 4\}\).

  • The intersection of two sets is a set such that if an object is a member of both sets, it is also a member of their intersection. That is, \(A \cap B = \{x : x \in A \land x \in B\}\). For example, \(A \cap B = \{2, 3\}\).

  • The complement of a set is a set such that if an object is a member of the set, it is not a member of its complement. However, if an object (within the universe) is not a member of the set, then it is a member of its complement. That is, \(A' = \{x : x \notin A\}\). For example, \(A' = \{4, 5\}\) (remembering the implicit \(x \in U\) criterion).

These can be used to construct some more operations:

  • The difference of two sets is a set of objects that are members of the first set but not the second. (Note that “first” and “second” are being used here now; the difference of sets is not commutative.) That is, \(A \setminus B = \{x : x \in A \land x \notin B\} = A \cap B'\). For example, \(A \setminus B = \{1\}\).

    • You can also use this to think of the complement as \(A' = U \setminus A\).

  • The symmetric or commutative difference of two sets is a set of objects that are members of either set but not the other. That is, \(A \ominus B = \{x : x \in A \oplus x \in B\} = A' \cup B'\). (Note: I am using the nonstandard notation \(\ominus\) for symmetric difference and \(\oplus\) for logical XOR.) For example, \(A \ominus B = \{1, 4\}\).

Checks#

  • Two sets are equal if every member of either set is also a member of the other set.

  • A set is a subset of another set if every member of the first set is also a member of the second. For example, \(\{1, 2\} \subseteq \{1, 2, 3\}\) but \(\{1, 2, 4\} \nsubseteq \{1, 2, 3\}\).

    • A set is a proper subset of another set if it is a subset of, but not equal to the other set. For example, \(\{1, 2\} \subset \{1, 2, 3\}\) but \(\{1, 2, 3\} \not\subset \{1, 2, 3\}\) even though \(\{1, 2, 3\} \subseteq \{1, 2, 3\}\).

    • You can also use this to think of equality as \(A = B \implies A \subseteq B \land B \subseteq A\).

  • A set is a superset (\(\supseteq\)) of another set if the other set is a subset of the set.

    • A set is a proper superset (\(\supset\)) of another set if the other set is a proper subset of the set.

Python Sets#

Python implements most of the set operations described above:

>>> {1, 2, 3} # set definition by listing members
{1, 2, 3}
>>> set() # the empty set
set()
>>> 1 in {1, 2, 3} # membership
True
>>> A = {1, 2, 3}
>>> B = {2, 3, 4}
>>> A | B # union (like OR)
{1, 2, 3, 4}
>>> A & B # intersection (like AND)
{2, 3}
>>> A - B # difference
{1}
>>> A ^ B # symmetric difference (like XOR)
{1, 4}
>>> {1, 2, 3} == {1, 2, 3} # equality, duh
True
>>> {1, 2} <= {1, 2, 3} # subset
True
>>> {1, 2} < {1, 2, 3} # proper subset
True
>>> {1, 2, 3} <= {1, 2, 3}
True
>>> {1, 2, 3} < {1, 2, 3}
False
>>> {1, 2, 4} <= {1, 2, 3}
False
>>> # flip sign and arguments for superset and proper superset

A notable omission from the Python set class, though, is the concept of a universe set. Furthermore, without a universe, there can be no complement, which would otherwise be ~A # like NOT.

Technicality

You could consider Python’s set comprehensions, like {x for x in range(5) if x % 2 == 1}, to be characteristic-based set definitions, where x % 2 == 1 is the characteristic. In that case, you could reasonably say that range(5) is the universe. However, Python sets don’t support universes in any other context, so the complement is still missing as a result.

However, drumroll…

Flag Instances as Sets#

Flag instances do what Python sets cannot! Namely, the subclass defines the universe. Because of this, flag instances support the complement, in addition to other set operations:

>>> class U(Flag):
...     """Definition of the universe"""
...     def __repr__(self) -> str:
...         """Hide the unimportant numeric enum value."""
...         return super().__repr__().split(':', 1)[0] + '>'
...     A = auto()
...     B = auto()
...     C = auto()
...     D = auto()
...     E = auto()
...
>>> U.A | U.B | U.C # set definition by listing members
<U.C|B|A>
>>> U(0) # the empty set
<U.0>
>>> U.A in U.A | U.B | U.C # membership
True
>>> X = U.A | U.B | U.C
>>> Y = U.B | U.C | U.D
>>> X | Y # union
<U.D|C|B|A>
>>> X & Y # intersection
<U.C|B>
>>> ~(U.A | U.B) # complement! :D
<U.E|D|C>
>>> X ^ Y # symmetric difference
<U.D|A>
>>> U.A | U.B | U.C == U.A | U.B | U.C # equality
True

However, using Flag instances as set stand-ins has its own drawbacks:

  • Some set operations are missing (but see this gist for an implementation of them):

    • Asymmetric difference (can’t do X - Y)

    • Superset and subset (can’t do X < Y or X > Y)

  • Obviously, you’re limited to the universe you define. Regular set instances can hold any hashable object. (That would make collections.abc.Hashable the universe if it was enumerable.)

  • set instances are mutable; Flag instances are not.

  • set instances can be nested; Flag instances cannot. Notably, each enum member is both a singleton set and the single member of that set at the same time.

So consider yourself informed.

Conclusion#

Regular Python set instances are mutable, nestable, and not bound to a universe, but as a consequence do not support the set complement. On the other hand, using enum.Flag to mimic sets does support the complement, since the enum definition is the universe, but native enum.Flag doesn’t support sub/super-set or asymmetric differences. (Again, see this gist for a custom subclass that does support those operations.)

To use an example from the original context in which I came up with this, Python sets are good for storing the groups/roles that a user belongs to / holds, while set-like flags are good for representing the permissions that a user has, possibly due to their groups/roles.

Do with this information what you will!

If you have something to say about this page, feel free to let me know!