Minimal hitting sets

mhs.py

#!/usr/bin/env python3
# -*- truncate-lines: t; -*-

# Yes, it is slow. But sufficient for small sets.
# Usage:
#
#   > import mhs
#   > list(mhs.mhs({9,11}, {2,3,6,9,10}))
#   [frozenset({9}),
#    frozenset({2, 11}),
#    frozenset({3, 11}),
#    frozenset({6, 11}),
#    frozenset({10, 11})]

from itertools import chain, combinations
from functools import reduce
from operator import or_

def powerset(iterable):
    """For any finite iterable, compute the power set (set of all subsets)."""
    xs = list(iterable)
    return map(frozenset, chain.from_iterable(combinations(xs, n) for n in range(len(xs) + 1)))

def hitting_sets(*sets):
    """For given set-like objects, compute all hitting sets.

    A hitting set is a set which contains at least on element of each set.
    """
    u = reduce(or_, sets, set())
    for p in powerset(u):
        if all(p & s for s in sets):
            yield p

def mhs(*sets):
    """For given set-like objects, compute all minimal hitting sets.

    A hitting set is minimal if it has no proper subset which is a hitting set, too.
    """
    for h in hitting_sets(*sets):
        if not any(p in hitting_sets(*sets) for p in powerset(h) if p != h):
            yield h

I have now turned this into a script, with its own repository: https://github.com/phipsgabler/mhs.