### program to check the Salzborn formulation of FUNC
### generates a bunch of random sets of specified size that separate the ground set, and looks for the minimal size of the resulting union-closed set system
ground_set = 19         # size of the ground set
generator_size = 9      # size of each generating set (try just below half of ground_set)
number_generators = 5   # number of generating sets to use (try rounding up log_2(ground_set), or at most one more)


current_record = 2^number_generators     # most pessimistic initial estimate of minimal set system size

while True:
    ### randomly pick number_generators many sets of size generator_size
    A = []
    for i in range(number_generators):
        generator = []
        while len(generator) < generator_size:
            new_element = ZZ.random_element(ground_set)
            while new_element in generator:
                new_element = ZZ.random_element(ground_set)
            generator.append(new_element)
        generator.sort()
        A.append(tuple(generator))

    ### first make sure that all points of the ground set appear somewhere, and abort if not
    admissible = True
    for x in range(ground_set):
        x_appears = False
        for i in range(len(A)):
            if x in A[i]:
                x_appears = True
        if not x_appears:
            admissible = False
    if not admissible:
        continue

    ### check whether the system of generators separates points, and abort if not
    separating = True
    for x in range(ground_set):
        for y in range(x+1,ground_set):
            xy_separated = False
            for i in range(len(A)):
                if x in A[i] and y not in A[i]:
                    xy_separated = True
                if x not in A[i] and y in A[i]:
                    xy_separated = True
            if not xy_separated:
                separating = False
    if not separating:
        continue

    ### take the union closure, and abort as soon as the current minimal size has been reached
    done = False
    abort = False
    while done == False and abort == False:
        newset_found = False
        for i in range(len(A)):
            for j in range(i+1,len(A)):
                candidate_union = uniq(A[i] + A[j])
                candidate_union.sort()
                candidate_union = tuple(candidate_union)
                if not candidate_union in A:
                    A.append(candidate_union)
                    newset_found = True
                    if (len(A) >= current_record):
                        abort = True
                if abort:
                    continue
            if abort:
                continue
        if newset_found == False:
            done = True
    if abort:
        continue

    ### now check the size of the union closure and output the system. It's guaranteed to be of minimal size
    print "Found system of size " + str(len(A)) + ", namely: " + str(A)
    current_record = len(A)

︠c0e37224-48ee-4642-a917-e5951f646beb︠
︠127b7426-d1f6-425f-9647-a04d69672386︠