find_minimal_labels.py

# Adjust this string to have your desired alphabet of letters
alphabet = "ABCDE"
# Adjust this list of strings to have the significantly different pairs
forbidden = ["AD", "AE", "CE", "DE"]
Then run!


def split_bads(universe, bad):
    left, right = bad
    modified = True
    new = []
    for a_group in universe:
        if left in a_group and right in a_group:
            new.append(a_group.replace(left, ""))
            new.append(a_group.replace(right, ""))
        else:
            new.append(a_group)
    return new

'''
A-B-E
|/|
C-D
'''

universes = [alphabet]
for bad in forbidden:
    print(universes)
    print("Breaking on", bad)
    universes = list(split_bads(universes, bad))
universes.sort(key=lambda u: len(u))
kept_universes = []
for i, u in enumerate(universes):
    exists_later = False
    for later_u in universes[i+1:]:
        if set(u).issubset(later_u):
            exists_later = True
    if not exists_later:
        kept_universes.append(u)
print(kept_universes)