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)
    
    combinations = []
    for i in range(1, q + 1):
        combination = list(it.product(map(str, range(1, q + 1)), repeat=i))
        combinations.extend(combination)

    for combination in combinations:
        matrix = matrices[combination[0]].copy()
        word = combination[0]
        for comb_i in range(1, len(combination)):
            matrix *= matrices[combination[comb_i]]
            word += combination[comb_i]
        matrices[word] = matrix

    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(input().split())

    combinations = []
    for i in range(1, gn + 1):
        combinations.extend(it.product(''.join(generators_list), repeat=i))

    result = {}
    for combination in combinations:
        correlation = []
        for i in elements:
            element = i
            for generator in combination:
                if element not in elements:
                    element = '*'
                else:
                    gi = generators_list.index(generator)
                    si = elements.index(element)
                    element = translations[gi][si]
            correlation.append(element)
        result[combination] = correlation

    find_correlation(result)


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()