Добавление второй лабы и тестов к остальнымHEADmaster

1 files changed, 391 insertions, 0 deletions

diff --git a/lab2/lab2.py b/lab2/lab2.py
new file mode 100644
index 0000000..e1616a9
--- /dev/null
+++ b/lab2/lab2.py
@@ -0,0 +1,391 @@
+import numpy as np
+import math
+import matplotlib.pyplot as plt
+
+
+def check_reflexivity(matrix):
+    diag_values = np.diagonal(matrix)
+    diag_values = np.unique(diag_values)
+    return int(diag_values.size == 1 and diag_values == [1])
+
+
+def check_antisymmetry(matrix):
+    new_matrix = np.multiply(matrix, matrix.T)
+    for i in range(len(new_matrix)):
+        for j in range(len(new_matrix[i])):
+            if i != j and new_matrix[i][j] != 0:
+                return 0
+    return 1
+
+
+def check_transitivity(matrix):
+    mlp_mx = np.matmul(matrix, matrix)
+    for i in range(len(mlp_mx)):
+        for j in range(len(mlp_mx[i])):
+            if mlp_mx[i][j] > 1:
+                mlp_mx[i][j] = 1
+    return int((mlp_mx <= matrix).all())
+
+
+def order_check(relation):
+    return check_antisymmetry(relation) and \
+            check_reflexivity(relation) and \
+            check_transitivity(relation)
+
+############################
+
+def reflexive_closure(matrix):
+    n = len(matrix)
+    for i in range(n):
+        matrix[i][i] = 1
+
+
+def symmetry_closure(matrix):
+    n = len(matrix)
+    for i in range(n):
+        for j in range(n):
+            if matrix[i][j]:
+                matrix[j][i] = 1
+
+
+def transitive_closure(matrix):
+    n = len(matrix)
+    for _ in range(n):
+        for i in range(n):
+            for j in range(n):
+                for k in range(n):
+                    if matrix[i][k] and matrix[k][j]:
+                        matrix[i][j] = 1
+
+
+def create_equivalent_closure(bin_relation):
+    relation = bin_relation.copy()
+    reflexive_closure(relation)
+    symmetry_closure(relation)
+    transitive_closure(relation)
+    return relation
+
+###################################
+
+def get_slices_list(relation_matrix, for_factor_set=1, attributes=None):
+    n = len(relation_matrix)
+    slices = []
+    for i in range(n):
+        slice = []
+        for j in range(n):
+            if relation_matrix[i][j]:
+                if attributes is None:
+                    slice.append(j + for_factor_set)
+                else:
+                    slice.append(attributes[j])
+        slices.append(slice)
+    return slices
+
+
+def create_factor_set(bin_relation):
+    slices = get_slices_list(bin_relation, 1, None)
+    print("Фактор-множество данной эквивалентности:")
+    print(set(map(tuple, slices)))
+    return slices
+
+
+def create_representative_system(factor_set):
+    factor_set = sorted(factor_set, key=len)
+    d = {}
+    representative_system = []
+    for eq_class in factor_set:
+        for representative in eq_class:
+            if representative not in representative_system:
+                d[representative] = eq_class
+                representative_system.append(representative)
+                break
+
+    print("Система представителей данного фактор-множества:")
+    print(representative_system)
+    for representative, eq_class in d.items():
+        print(representative, "принадлежит множеству", eq_class)
+
+
+####################################################
+
+def get_dividers(l):
+    d = {}
+    for elem in l:
+        dividers = []
+        for divider in l:
+            if elem % divider == 0:
+                dividers.append(divider)
+        d[elem] = dividers
+
+    return d
+
+
+def get_min_elem(objects, elements, k=0):
+    min_elements = []
+    for i in range(k, len(objects)):
+        is_min = True
+        for j in range(k, len(objects)):
+            if objects[j][i] != 0 and i != j:
+                is_min = False
+        if is_min:
+            min_elements.append(elements[i])
+    return min_elements
+
+
+def get_max_elem(some_set, objs, k=0):
+    max_elements = []
+    for i in range(k, len(some_set)):
+        is_max = True
+        for j in range(k, len(some_set)):
+            if some_set[i][j] != 0 and i != j:
+                is_max = False
+        if is_max:
+            max_elements.append(objs[i])
+
+    return max_elements
+
+
+def get_least_elem(some_set, objs):
+    min_elem_list = get_min_elem(some_set, objs)
+    if len(min_elem_list) != 1:
+        return None
+    else:
+        return min_elem_list[0]
+
+
+def get_greatest_elem(some_set, objs):
+    max_elem_list = get_max_elem(some_set, objs)
+    if len(max_elem_list) != 1:
+        return None
+    else:
+        return max_elem_list[0]
+
+
+def get_order_set_elem():
+    objs = []
+    print('Введите элементы множества:')
+    objs = input().split()
+    print("Введите значения матрицы бинарного отношения:")
+    n = len(objs)
+    entries = [list(map(int, input().split())) for i in range(n)]
+    some_set = np.array(entries).reshape(n, n)
+    if not order_check(some_set):
+        print("Введённое отношение не является отношением порядка")
+        return 0
+
+    print("Минимальные элементы в множестве:", get_min_elem(some_set, objs))
+    print("Максимальные элементы в множестве:", get_max_elem(some_set, objs))
+    print("Наименьший элемент в множестве:", get_least_elem(some_set, objs))
+    print("Наибольший элемент в множестве:", get_greatest_elem(some_set, objs))
+
+###########################################
+
+def get_dividers_list(n):
+    dividers_list = [1]
+    for i in range(2, int(math.sqrt(n)) + 1):
+        if n % i == 0:
+            dividers_list.append(i)
+            dividers_list.append(n // i)
+    dividers_list.append(n)
+    return sorted(dividers_list)
+
+
+def make_hasse():
+    print('Введите элементы множества:')
+    objs = input().split()
+    n = len(objs)
+    print("Введите значения матрицы бинарного отношения:")
+    entries = [list(map(int, input().split())) for _ in range(n)]
+    some_set = np.array(entries).reshape(n, n)
+    if not order_check(some_set):
+        print("Введенное отношение не является отношением порядка")
+        return []
+
+    hasse_levels = {key: 1 for key in objs}
+    i = 0
+    some_k = 0
+    while True:
+        min_elems = get_min_elem(some_set, objs, some_k)
+        i += 1
+
+        if not min_elems:
+            break
+
+        for elem in min_elems:
+            hasse_levels[elem] = i
+
+        some_k += len(min_elems)
+
+    connected_values_dict = {}
+    for key, value in hasse_levels.items():
+        lvl_diff = 1
+        connected_values = []
+        relation_list = get_slices_list(some_set, 0, objs)[objs.index(key)]
+        for i in relation_list:
+            if hasse_levels[i] == value + lvl_diff:
+                connected_values.append(i)
+
+        connected_values = list(set(connected_values))
+        connected_values.sort()
+        connected_values_dict[key] = connected_values
+
+    hasse_data = []
+    for i in hasse_levels:
+        hasse_data.append([i, hasse_levels[i], connected_values_dict[i]])
+
+    # связи здесь построены снизу-вверх
+    return hasse_data
+
+
+def visualize_hasse(hasse_data):
+    plt.xlim(-1.0, len(hasse_data) * 2)
+    plt.ylim(0, len(hasse_data) * 3 + 1.5)
+
+    lvl_to_elems = {key[1]: 0 for key in hasse_data}
+    for hasse_elem in hasse_data:
+        for level in lvl_to_elems:
+            if hasse_elem[1] == level:
+                lvl_to_elems[level] += 1
+
+    max_lvl_elem_amount = lvl_to_elems[max(lvl_to_elems, key=lvl_to_elems.get)]
+
+    lvl = 4
+    elem_address = {}
+    for hasse_elem in hasse_data:
+        elem_lvl = hasse_elem[1]
+        elem = hasse_elem[0]
+        hasse_elem_y = elem_lvl * lvl
+        hasse_elem_x = 1.5 * (max_lvl_elem_amount - lvl_to_elems[elem_lvl])
+        lvl_to_elems[elem_lvl] += -1
+        plt.text(hasse_elem_x - 0.1, hasse_elem_y - 0.1, f'{elem}')
+        plt.scatter(hasse_elem_x + 0.1, hasse_elem_y + 0.1, s=350, facecolors='none', edgecolors='black')
+        elem_address[elem] = [hasse_elem_x + 0.1, hasse_elem_y + 0.1]
+
+    for hasse_elem in hasse_data:
+        x1, y1 = elem_address[hasse_elem[0]][0], elem_address[hasse_elem[0]][1]
+        for connected_elem in hasse_elem[2]:
+            plt.plot([x1, elem_address[connected_elem][0]],
+                     [y1 + 1, elem_address[connected_elem][1] - 1],
+                     color="black")
+
+    plt.show()
+
+#########################################################
+
+def get_closure_system(rel_matrix, objs, attrs):
+    closure_system = [objs]
+    row_slices = get_slices_list(rel_matrix.copy().T, 1, objs)
+    is_empty_included = False
+    for attr_i in range(len(attrs)):
+        after_intersection = [list(row_slices[attr_i])]
+        for closure_i in range(len(closure_system)):
+            cs_set = set(closure_system[closure_i])
+            intersection = set(row_slices[attr_i]) & cs_set
+            intersection = sorted(intersection)
+            if intersection not in after_intersection \
+                    and intersection or not is_empty_included:
+                after_intersection.append(intersection)
+
+            if not intersection:
+                is_empty_included = True
+
+        if after_intersection not in closure_system:
+            closure_system += after_intersection
+
+    new_closure_system = []
+    for closure in closure_system:
+        if closure not in new_closure_system:
+            new_closure_system.append(closure)
+
+    print("Система замыканий:", new_closure_system)
+    return closure_system
+
+
+def get_context(closure, rel_matrix, objs, attrs):
+    if not closure:
+        context = attrs
+    else:
+        column_slices = get_slices_list(rel_matrix, 1, attrs)
+        list_of_sets = []
+        for elem in closure:
+            obj_i = objs.index(elem)
+            list_of_sets.append(set(column_slices[obj_i]))
+
+        context = list_of_sets[0]
+        for cur_set in list_of_sets:
+            context = context.intersection(cur_set)
+
+    return sorted(context)
+
+
+def make_lattice_concept():
+    print("Введите элементы множества:")
+    objects = input().split()
+    print("Введите множество атрибутов:")
+    attributes = input().split()
+    print('Введите матрицу отношения на декартовом произведении множеств объектов и атрибутов:')
+    entries = []
+    for _ in range(len(objects)):
+        entries.extend(map(int, input().split()))
+    relation_matrix = np.array(entries).reshape(len(objects), len(attributes))
+    closure_system = get_closure_system(relation_matrix, objects, attributes)
+
+    lattice_concept = []
+    for closure in closure_system:
+        context = get_context(closure, relation_matrix, objects, attributes)
+        concept = closure, context
+        lattice_concept.append(concept)
+
+    new_lattice_concept = []
+    for concept in lattice_concept:
+        if concept not in new_lattice_concept:
+            new_lattice_concept.append(concept)
+
+    print("Решетка концептов:", new_lattice_concept)
+
+##################################################
+
+def main():
+    print("1. Эквивалентное замыкание, система представителей")
+    print("2. минимальные и максимальные элементы")
+    print("3. Построение диаграммы Хассе")
+    print("4. Построение решётки концептов")
+    task = int(input("Выберите задачу: "))
+
+    if task == 1:
+        n = int(input("Введите размер матрицы: "))
+        l = []
+
+        print(f"На следующих {n} строках введите матрицу:")
+        for _ in range(n):
+            l.extend(map(int, input().split()))
+        matrix = np.array(l, dtype=bool).reshape(n, n)
+
+        # 1 - эквивалентное замыкание
+        eq = create_equivalent_closure(matrix)
+        print("Матрица эквивалентного замыкания:")
+        print(eq.astype(int))
+
+        # 2 - система представителей
+        factor_set = create_factor_set(matrix)
+        create_representative_system(factor_set)
+
+    elif task == 2:
+
+        # 3 - минимальные (максимальные) и наименьший (наибольший) элементы множества
+        get_order_set_elem()
+    
+    elif task == 3:
+        # 4 - Диаграмма Хассе
+        hasse_data = make_hasse()
+        if hasse_data:
+            print(hasse_data)
+            visualize_hasse(hasse_data)
+
+    elif task == 4:
+        # 5 - Решётка концептов
+        make_lattice_concept()
+
+
+if __name__ == "__main__":
+    main()
\ No newline at end of file