Search This Blog

Generating a minimal set algebra from a given set of sets

This is a Python program which generates the minimal set algebra which contains all the elements/sets of the set C. In this program Omega is the universal set. Then C is a subset of the powerset of Omega. The program generates the minimal set algebra C3 which contains all the elements of C. A set algebra is also known as a field of sets. Of course here Omega and C are both finite sets. 

       
import itertools as it

Empty = frozenset({})


def main():
    # Omega ---> the universal set
    Omega = frozenset({1, 2, 3, 4, 5, 6})

    # C ---> a set of subsets of Omega

    # C = {frozenset({1}), frozenset({1,3})}
    # C = {frozenset({1,2}), frozenset({2,3,4}), frozenset({5})}

    C = {frozenset({1, 2}), frozenset({2, 3, 5})}

    # Now we generate the sets C1, C2, C3

    # C3 is the minimal boolean algebra
    # which contains all the elements of C

    print("=" * 60)
    C1 = gen_C1(Omega, C)
    C2 = gen_C2(Omega, C1)
    C3 = gen_C3(Omega, C2)

    print("The set of sets C is given as input.")
    print("Size: ", len(C), "---> C = ", make_lst(C))
    print("Added all complements to C ---> result: C1")
    print("Size: ", len(C1), "---> C1 = ", make_lst(C1))

    print("Added all intersections to C1 ---> result: C2")
    print("Size: ", len(C2), "---> C2 = ", make_lst(C2))

    print("Added all unions of disjoint sets to C2 ---> result: C3")
    print("Size: ", len(C3), "---> C3 = ", make_lst(C3))

    print("Checking if C3 is indeed a set algebra ---> ", is_set_algebra(Omega, C3))

    print("=" * 60)


def make_lst(C):
    P = []
    for A in C:
        P.append(str(set(A)) if not Empty == A else "{}")
    return P


def powerset(Omega):
    n = len(Omega)
    ps = set({})

    for k in range(0, n + 1):
        z = it.combinations(Omega, k)
        for t in z:
            ps.add(frozenset(t))

    return ps


def gen_C1(Omega, C):
    ps = powerset(Omega)
    C1 = frozenset({})
    C1 = C1 | {Empty}
    C1 = C1 | {Omega}
    for A in C:
        C1 = C1 | {A}
        C1 = C1 | {Omega - A}

    return C1


def gen_C2(Omega, C1):
    P = Empty
    k = 0

    while (True):
        k = k + 1
        sz1 = len(P)
        Z = Empty
        S = C1 if k == 1 else P

        for A in S:
            for B in S:
                Z = Z | {A & B}

        P = P | Z

        sz2 = len(P)
        if sz2 == sz1:
            break

    return P


def gen_C3(Omega, C2):
    P = Empty
    k = 0

    while True:
        k = k + 1
        sz1 = len(P)
        Z = Empty
        S = C2 if k == 1 else P

        for A in S:
            for B in S:
                # print("A=",A)
                # print("B=",B)
                if A & B == Empty or A & B == A or A & B == B:
                    # print("Adding to Z ...")
                    Z = Z | {A | B}

        P = P | Z

        sz2 = len(P)
        if sz2 == sz1:
            break

    return P


def is_set_algebra(Omega, U):
    if Omega not in U:
        return False

    if Empty not in U:
        return False

    for A in U:
        B = Omega - A
        if B not in U:
            return False

    for A in U:
        for B in U:
            if not (A | B in U):
                return False
            if not (A & B in U):
                return False

    return True


if __name__ == "__main__":
    main()


       

No comments:

Post a Comment