Check if a set family is a matroid

check_matroid.py

#!/usr/bin/env python3

import ast


def check_matroid(indsets):
    if () not in indsets:
        return ()

    # check hereditary
    for S in indsets:
        if S:
            for x in S:
                L = list(S)
                L.remove(x)
                if tuple(L) not in indsets:
                    return (S, x)

    # check augmentation
    for S_1 in indsets:
        for S_2 in indsets:
            if len(S_1) < len(S_2):
                valid = False
                for x in set(S_2) - set(S_1):
                    S_3 = set(S_1)
                    S_3.add(x)
                    if tuple(sorted(S_3)) in indsets:
                        valid = True
                if not valid:
                    return (S_1, S_2)
    return True


if __name__ == '__main__':
    indsets = set()
    for S in ast.literal_eval(input()):
        indsets.add(tuple(sorted(set(S))))
    print(check_matroid(indsets))