Last active
October 21, 2015 20:48
-
-
Save phipsgabler/bb7b294738426a544fe9 to your computer and use it in GitHub Desktop.
Minimal hitting sets
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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 | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I have now turned this into a script, with its own repository: https://github.com/phipsgabler/mhs.