输入：关系矩阵 M（n×n）
输出：传递闭包的矩阵

for k from 1 to n:
    for i from 1 to n:
        for j from 1 to n:
            M[i][j] = M[i][j] OR (M[i][k] AND M[k][j])

"""
关系性质检查和运算
"""


class Relation:
    """二元关系类"""
    
    def __init__(self, elements, pairs):
        """
        初始化关系
        
        参数:
            elements: 集合A的元素列表
            pairs: 关系中的有序对列表 [(a,b), ...]
        """
        self.elements = sorted(elements)
        self.pairs = set(pairs)
        self.n = len(self.elements)
        self.index = {elem: i for i, elem in enumerate(self.elements)}
    
    def is_reflexive(self):
        """检查是否自反"""
        return all((a, a) in self.pairs for a in self.elements)
    
    def is_symmetric(self):
        """检查是否对称"""
        return all((b, a) in self.pairs for (a, b) in self.pairs)
    
    def is_antisymmetric(self):
        """检查是否反对称"""
        for (a, b) in self.pairs:
            if a != b and (b, a) in self.pairs:
                return False
        return True
    
    def is_transitive(self):
        """检查是否传递"""
        for (a, b) in self.pairs:
            for (c, d) in self.pairs:
                if b == c and (a, d) not in self.pairs:
                    return False
        return True
    
    def is_equivalence(self):
        """检查是否是等价关系"""
        return self.is_reflexive() and self.is_symmetric() and self.is_transitive()
    
    def is_partial_order(self):
        """检查是否是偏序关系"""
        return self.is_reflexive() and self.is_antisymmetric() and self.is_transitive()
    
    def inverse(self):
        """计算逆关系"""
        return Relation(self.elements, [(b, a) for (a, b) in self.pairs])
    
    def compose(self, other):
        """
        复合关系：self ∘ other
        先应用other，再应用self
        """
        composed = set()
        for (a, b) in other.pairs:
            for (c, d) in self.pairs:
                if b == c:
                    composed.add((a, d))
        return Relation(self.elements, list(composed))
    
    def reflexive_closure(self):
        """自反闭包"""
        new_pairs = self.pairs | {(a, a) for a in self.elements}
        return Relation(self.elements, list(new_pairs))
    
    def symmetric_closure(self):
        """对称闭包"""
        new_pairs = self.pairs | {(b, a) for (a, b) in self.pairs}
        return Relation(self.elements, list(new_pairs))
    
    def transitive_closure_warshall(self):
        """使用Warshall算法计算传递闭包"""
        # 初始化矩阵
        M = [[False] * self.n for _ in range(self.n)]
        for (a, b) in self.pairs:
            i, j = self.index[a], self.index[b]
            M[i][j] = True
        
        # Warshall算法
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    M[i][j] = M[i][j] or (M[i][k] and M[k][j])
        
        # 转换回有序对
        pairs = []
        for i in range(self.n):
            for j in range(self.n):
                if M[i][j]:
                    pairs.append((self.elements[i], self.elements[j]))
        
        return Relation(self.elements, pairs)
    
    def equivalence_classes(self):
        """
        计算等价类（仅当是等价关系时有效）
        
        返回: 等价类列表，每个等价类是元素列表
        """
        if not self.is_equivalence():
            raise ValueError("不是等价关系")
        
        visited = set()
        classes = []
        
        for a in self.elements:
            if a not in visited:
                eq_class = [b for b in self.elements if (a, b) in self.pairs]
                classes.append(sorted(eq_class))
                visited.update(eq_class)
        
        return classes
    
    def __repr__(self):
        return f"Relation({self.elements}, {sorted(self.pairs)})"


def demonstrate_relation_properties():
    """演示关系性质检查"""
    
    print("=== 关系性质检查 ===\n")
    
    elements = [1, 2, 3]
    
    # 等价关系：模3同余（在{1,2,3}上简化）
    R1 = Relation(elements, [(1,1), (2,2), (3,3)])
    print(f"R1 = {R1}")
    print(f"  自反: {R1.is_reflexive()}")
    print(f"  对称: {R1.is_symmetric()}")
    print(f"  反对称: {R1.is_antisymmetric()}")
    print(f"  传递: {R1.is_transitive()}")
    print(f"  等价关系: {R1.is_equivalence()}")
    print(f"  偏序关系: {R1.is_partial_order()}")
    
    # 偏序关系：≤
    R2 = Relation(elements, [
        (1,1), (2,2), (3,3),
        (1,2), (1,3), (2,3)
    ])
    print(f"\nR2 = {R2}")
    print(f"  自反: {R2.is_reflexive()}")
    print(f"  对称: {R2.is_symmetric()}")
    print(f"  反对称: {R2.is_antisymmetric()}")
    print(f"  传递: {R2.is_transitive()}")
    print(f"  等价关系: {R2.is_equivalence()}")
    print(f"  偏序关系: {R2.is_partial_order()}")
    
    # 传递闭包
    R3 = Relation(elements, [(1,2), (2,3)])
    print(f"\nR3 = {R3}")
    tc = R3.transitive_closure_warshall()
    print(f"  传递闭包: {tc}")


def demonstrate_equivalence_classes():
    """演示等价类"""
    
    print("\n=== 等价类 ===\n")
    
    # 模3同余关系（在0-8上）
    elements = list(range(9))
    pairs = [(a, b) for a in elements for b in elements if a % 3 == b % 3]
    
    R = Relation(elements, pairs)
    print(f"模3同余关系在{{0,...,8}}上")
    print(f"  是等价关系: {R.is_equivalence()}")
    
    classes = R.equivalence_classes()
    print(f"  等价类: {classes}")


if __name__ == "__main__":
    demonstrate_relation_properties()
    demonstrate_equivalence_classes()

"""
哈斯图生成和偏序集分析
"""


class Poset:
    """偏序集类"""
    
    def __init__(self, elements, leq_pairs):
        """
        初始化偏序集
        
        参数:
            elements: 元素列表
            leq_pairs: 偏序关系中的有序对（包括自反对）
        """
        self.elements = sorted(elements)
        self.leq = set(leq_pairs)
        self.n = len(self.elements)
        self.index = {elem: i for i, elem in enumerate(self.elements)}
    
    def strict_less(self, a, b):
        """检查 a < b（严格小于）"""
        return (a, b) in self.leq and a != b
    
    def covers(self, a, b):
        """
        检查 a 是否覆盖 b（即 a < b 且不存在 c 使得 a < c < b）
        注意：这里 a < b 表示 a 在哈斯图中位于 b 下方
        """
        if not self.strict_less(a, b):
            return False
        
        for c in self.elements:
            if c != a and c != b:
                if self.strict_less(a, c) and self.strict_less(c, b):
                    return False
        
        return True
    
    def hasse_edges(self):
        """
        获取哈斯图的边
        
        返回: 有序对列表 [(lower, upper), ...]
        """
        edges = []
        for a in self.elements:
            for b in self.elements:
                if self.covers(a, b):
                    edges.append((a, b))
        return edges
    
    def minimal_elements(self):
        """找出极小元"""
        minimals = []
        for a in self.elements:
            is_minimal = True
            for b in self.elements:
                if b != a and self.strict_less(b, a):
                    is_minimal = False
                    break
            if is_minimal:
                minimals.append(a)
        return minimals
    
    def maximal_elements(self):
        """找出极大元"""
        maximals = []
        for a in self.elements:
            is_maximal = True
            for b in self.elements:
                if b != a and self.strict_less(a, b):
                    is_maximal = False
                    break
            if is_maximal:
                maximals.append(a)
        return maximals
    
    def print_hasse_diagram(self):
        """文本形式打印哈斯图"""
        edges = self.hasse_edges()
        print("哈斯图的边（从下到上）:")
        for (a, b) in edges:
            print(f"  {a} -- {b}")
        
        print(f"\n极小元: {self.minimal_elements()}")
        print(f"极大元: {self.maximal_elements()}")


def demonstrate_poset():
    """演示偏序集"""
    
    print("=== 偏序集：整除关系 ===\n")
    
    # {1, 2, 3, 4, 6, 12} 上的整除关系
    elements = [1, 2, 3, 4, 6, 12]
    pairs = [(a, b) for a in elements for b in elements if b % a == 0]
    
    poset = Poset(elements, pairs)
    poset.print_hasse_diagram()
    
    print("\n=== 偏序集：子集包含 ===\n")
    
    # P({1,2,3}) 上的包含关系
    from itertools import chain, combinations
    
    def powerset(iterable):
        s = list(iterable)
        return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
    
    subsets = [tuple(sorted(s)) for s in powerset([1, 2, 3])]
    pairs = [(a, b) for a in subsets for b in subsets if set(a).issubset(set(b))]
    
    poset2 = Poset(subsets, pairs)
    poset2.print_hasse_diagram()


if __name__ == "__main__":
    demonstrate_poset()