Automorphisms-on-Posets/automorphismsBasic.py at main · mehekmehra/Automorphisms-on-Posets · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
from sympy.combinatorics.named_groups import SymmetricGroup
from sympy.combinatorics.perm_groups import PermutationGroup
import numpy as np

# automorphisms and automorphism checker provide information about automorphisms of posets.
# Ensure that you follow the conventions for inputs and that your input is in fact a poset.
# I am planning to update this with a poset checker and possibly a converter to make inputs simpler.

def automorphisms(myArr):
    """ automorphisms takes in an array representation of a matrix (less than matrix, similar to adjacency)
        and returns the number of automorphisms and the mappings (as permutations)

        parameters: myArr: an array representation of a matrix where less than/equal to relations
                            are represented by 1s by rows and non adjacent/ greater than relations
                            are 0s. (see the examples and the reference picture)

        output: automorphism counter: returns the number of automorphisms
                permutations: prints the mappings as permutations
                                (eg 0 -> 1, 1 -> 0, 0 -> 0 would be [1, 0, 2])
    """

    posetArr = np.array(myArr)
    possibleMaps = permutationGroup(myArr)
    autCount = 0
    elements = elementList(myArr)

    for permutation in possibleMaps:
        possiblePoset = np.array(myArr)
        # swap cols
        possiblePoset[:] = possiblePoset[:, permutation]
        # swap rows
        possiblePoset[elements] = possiblePoset[permutation]

        if (possiblePoset == posetArr).all():
            autCount += 1
            print(permutation)

    return autCount

def automorphismChecker(myArr, autPermutation):
    """ automorphismChecker takes in an array representation of a matrix (less than matrix, similar to adjacency)
        and a permutation, and returns a boolean

        parameters: myArr: an array representation of a matrix where less than/equal to relations
                            are represented by 1s by rows and non adjacent/ greater than relations
                            are 0s. (see the examples and the reference picture)

                    autPermutation: a list representation of the permutation
                                    (eg 0 -> 1, 1 -> 0, 0 -> 0 would be [1, 0, 2])

        output: boolean: True if autPermutation is an automorphism on myArr.
                         False if it is not.
    """
    posetArr = np.array(myArr)
    elements = elementList(myArr)
    possiblePoset = np.array(myArr)

    possiblePoset[:] = possiblePoset[:, autPermutation]
    possiblePoset[elements] = possiblePoset[autPermutation]

    if (possiblePoset == posetArr).all():
        return True
    else:
        return False

def permutationGroup(myArr):
    """ permutationGroup outputs the permutation group for all of the nodes in a given poset matrix
        primarily a helper function

        parameters: myArr: an array representation of a matrix where less than/equal to relations
                            are represented by 1s by rows and non adjacent/ greater than relations
                            are 0s. (see the examples and the reference picture)

        output: permutations: a list of the permutaions in the permutation group
    """
    generators = SymmetricGroup(len(myArr))
    permutations = list(generators.generate_schreier_sims(af=True))
    return permutations


def elementList(myArr):
    """ elementList outputs a list of the nodes in myArr
        primarily a helper function

        parameters: myArr: an array representation of a matrix where less than/equal to relations
                            are represented by 1s by rows and non adjacent/ greater than relations
                            are 0s. (see the examples and the reference picture)

        output: a list of nodes.
    """
    elementsList = []
    start = 0
    for x in range(len(myArr)):
        elementsList += [start]
        start += 1
    return elementsList


##############
## examples ##
##############

# test 1
# test = [[1, 1, 1, 0], [0, 1, 0, 1], [0, 0, 1, 1], [0, 0, 0, 1]]
# print(automorphisms(test))

# test 2: chain
# test = [[1, 1, 0, 0, 0], [0, 1, 1, 0, 0], [0, 0, 1, 1, 0], [0, 0, 0, 1, 1], [0, 0, 0, 0, 1]]
# print(automorphisms(test))

# test 3: separate
# test = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
# print(automorphisms(test))

# test 4:
# test = [[1, 1, 1, 1, 0], [0, 1, 0, 0, 1], [0, 0, 1, 0, 1], [0, 0, 0, 1, 1], [0, 0, 0, 0, 1]]
# print(automorphisms(test))

# test 5:
# test = [[1, 1, 1, 1, 0, 0], [0, 1, 0, 0, 1, 0], [0, 0, 1, 0, 1, 0], [0, 0, 0, 1, 1, 0], [0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 1]]
# print(automorphisms(test))

# test 6:
# test = [[1, 1, 1, 0, 0], [0, 1, 0, 0, 1], [0, 0, 1, 0, 1], [0, 0, 0, 1, 1], [0, 0, 0, 0, 1]]
# print(automorphisms(test))