diff options
Diffstat (limited to 'lab5')
| -rw-r--r-- | lab5/lab5.py | 178 |
1 files changed, 178 insertions, 0 deletions
diff --git a/lab5/lab5.py b/lab5/lab5.py new file mode 100644 index 0000000..5cf5027 --- /dev/null +++ b/lab5/lab5.py @@ -0,0 +1,178 @@ +import numpy as np + + +def check_associativity(cayley: np.array, semigroup: list) -> bool: + n = cayley.shape[0] + for i in range(n): + for j in range(n): + for k in range(n): + q = semigroup.index(cayley[i, k]) + p = semigroup.index(cayley[j, i]) + if cayley[p, k] != cayley[j, q]: + return False + return True + + +def get_right_ideal(element, semigroup, cayley): + i = semigroup.index(element) + return set(cayley[i]) + + +def get_left_ideal(element, semigroup, cayley): + i = semigroup.index(element) + return set(cayley.T[i]) + + +def get_semigroup_ideals(semigroup, cayley): + right_ideals = {} + left_ideals = {} + for element in semigroup: + right_ideals[element] = get_right_ideal(element, semigroup, cayley) + left_ideals[element] = get_left_ideal(element, semigroup, cayley) + return right_ideals, left_ideals + + +def create_table(semigroup, translations): + cayley = [] + for i in semigroup: + row = [] + for j in semigroup: + word = i + j + word = translate_word(word, translations) + row.append(word) + cayley.append(row) + return np.array(cayley) + + +def translate_word(word, translations): + while True: + tmp = word + for key, val in translations: + word = word.replace(key, val) + if tmp == word: + break + return word + + +def create_grin_relation(semigroup, right_ideals, left_ideals): + n = len(semigroup) + r = np.zeros((n, n), dtype=bool) + l = np.zeros((n, n), dtype=bool) + for i in range(n): + for j in range(n): + element1 = semigroup[i] + element2 = semigroup[j] + r[i][j] = (right_ideals[element1] == right_ideals[element2]) + l[i][j] = (left_ideals[element1] == left_ideals[element2]) + return r, l + + +def dfs(graph, used, v, l, is_transposed=False): + used[v] = True + + if is_transposed: + l.append(v) + + for i in range(len(graph)): + if not(used[i]) and graph[v][i]: + dfs(graph, used, i, l, is_transposed) + + if not is_transposed: + l.append(v) + + +def get_egg_box(grin_relation, semigroup): + n = len(grin_relation) + used = np.zeros(n) + + component = [] + order = [] + + for i in range(n): + if not used[i]: + dfs(grin_relation, used, i, order) + + used = np.zeros(n) + egg_box = [] + for i in range(n): + v = order[n - 1 - i] + if not used[v]: + dfs(grin_relation.T, used, v, component, True) + egg_box.append(component.copy()) + component.clear() + + return [[semigroup[elem] for elem in egg] for egg in egg_box] + + +def print_cayley(semigroup, cayley): + n = len(semigroup) + m = max(np.char.str_len(cayley.flatten())) + print(' ' * (m + 2) + '\u2502', end='') + for i in range(n): + print(semigroup[i].rjust(m + 1, ' ') + ' ', end='') + print() + print('\u2500' * (m + 2) + '\u253C' + '\u2500' * ((m + 2) * n)) + for i in range(n): + print(semigroup[i].rjust(m + 1, ' ') + ' \u2502', end='') + for j in range(n): + print(cayley[i, j].rjust(m + 1, ' '), end=' ') + print() + + +def make_semigroup(): + print("Введите элементы полугруппы:") + semigroup = set(input().split()) + + print("Введите количество преобразований:") + k = int(input()) + + translations = [] + for _ in range(k): + print(f"Введите преобразование: ") + key, val = input().split() + translations.append((key, val)) + + while True: + new_elements = set() + for i in semigroup: + for j in semigroup: + word = i + j + word = translate_word(word, translations) + new_elements.add(word) + tmp = semigroup.copy() + semigroup |= new_elements + if tmp == semigroup: + break + + semigroup = list(semigroup) + semigroup.sort() + + return semigroup, translations + + +def main(): + semigroup, translations = make_semigroup() + print("Полугруппа:") + print(semigroup) + + print("Таблица Кэли:") + cayley = create_table(semigroup, translations) + print_cayley(semigroup, cayley) + + if not check_associativity(cayley, semigroup): + print("Ассоциативность для данной таблицы Кэли не выполняется") + return + + print("Отношение Грина:") + right_ideals, left_ideals = get_semigroup_ideals(semigroup, cayley) + r, l = create_grin_relation(semigroup, right_ideals, left_ideals) + d = r + l + print(d.astype(int)) + + print("egg-box диаграмма:") + egg_box = get_egg_box(d, semigroup) + print(egg_box) + + +if __name__ == "__main__": + main()
\ No newline at end of file |