import numpy as np
import itertools as it


def make_subsemigroup():
    print("Введите элементы множества:")
    elements = input().split()
    n = len(elements)

    print("Введите элементы подмножества:")
    subelements = input().split()

    print("Введите значения таблицы Кэли:")
    cayley = []
    for _ in range(n):
        cayley.append(input().split())
    cayley = np.array(cayley)

    x_i = subelements[:]
    while True:
        x_l = []
        for x in x_i:
            for y in subelements:
                x_l.append(cayley[elements.index(x)][elements.index(y)])
        tmp = list(set(x_i) | set(x_l))
        tmp.sort()

        if tmp == x_i:
            break

        x_i = tmp[:]

    print("Подполугруппа:")
    print(x_i)


def find_correlation(matrices):
    result = {}
    correlations = {}
    for key, value in matrices.items():
        if not any(np.array_equal(value, i) for i in result.values()):
            result[key] = value
        else:
            for k, v in result.items():
                if np.array_equal(v, value):
                    correlations[key] = k

    print("Копредставления:")
    for key, value in result.items():
        print(f"{''.join(key)}:")
        print(value)

    print("Полученные соотношения:")
    for key, value in correlations.items():
        print(''.join(key), "->", ''.join(value))


def make_semigroup_binrel():
    print("Введите элементы множества:")
    elements = input().split()
    n = len(elements)

    print("Введите количество бинарных отношений:")
    q = int(input())

    matrices = {}
    for i in range(q):
        print("Введите значения матрицы:")
        matrix = []
        for _ in range(n):
            matrix.append(list(map(int, input().split())))
        matrices[str(i + 1)] = np.array(matrix)

    while True:
        new_matrices = {}
        for key_i, value_i in matrices.items():
            for key_j, value_j in matrices.items():
                new_matrices[key_i + key_j] = value_i * value_j

        already_exists = []
        for mat in new_matrices.values():
            flags = []
            for mat_old in matrices.values():
                flags.append(np.array_equal(mat, mat_old))
            already_exists.append(any(flags))
            if not any(flags):
                break

        if all(already_exists):
            break

        matrices.update(new_matrices)

    find_correlation(matrices)
    

def make_semigroup():
    print("Введите элементы полугруппы:")
    elements = input().split()
    n = len(elements)

    print("Введите элементы множества преобразований:")
    generators_list = input().split()
    gn = len(generators_list)

    translations = []
    for i in range(gn):
        print(f"Введите значения преобразования '{generators_list[i]}' "
               "элементов полугруппы:")
        print(*elements)
        translations.append((generators_list[i], input().split()))

    copresentation = translations.copy()
    correlations = {}
    while True:
        is_inserted = False
        for key_i, value_i in translations:
            for key_j, value_j in copresentation:
                new_word = key_i + key_j

                new_value = []
                for elem in value_i:
                    if elem == "*":
                        sec_sem = "*"
                    else:
                        sec_sem = value_j[int(elem) - 1]
                    new_value.append(sec_sem)

                find_corr = False
                for k, v in copresentation:
                    if np.array_equal(new_value, v):
                        correlations[new_word] = k
                        find_corr = True
                if not find_corr:
                    copresentation.append((new_word, new_value))
                    is_inserted = True
        if not is_inserted:
            break

    print("Копредставление: ")
    for key, value in copresentation:
        print(key + ":", value)

    print("Полученные соотношения: ")
    for key, value in correlations.items():
        print(key, "->", value)


def main():
    flag = input("Построить подполугруппу по таблице Кэли? (да/НЕТ) ")
    if flag.lower() == "да":
        make_subsemigroup()

    flag = input("Построить полугруппу бинарных отношений по порождающему "
                 "множеству? (да/НЕТ) ")
    if flag.lower() == "да":
        make_semigroup_binrel()

    flag = input("Построить полугруппу по порождающему множеству и "
                 "определяющим соотношениям? (да/НЕТ) ")
    if flag.lower() == "да":
        make_semigroup()


if __name__ == "__main__":
    main()