Теория групп и Python

Question

Как написать код Python, чтобы проверить, является ли операция ∗ на множестве {0,1,..,n−1}, определенной таблицей Кэли, ассоциативной или нет.

Мой попытался код:

def is_associative_cayley_table(table):
    if not is_cayley_table(table):
        return False

    for i in range (0,len(table)):
        for j in range (0,len(table)):
            for k in range (0,len(table)):
                if (table[table[i][j])][k])==(table[i][(table[j][k])]):
                   print("Okay")
                else
                   return False

Answer 1

Вместо печати "Okay"n^3 раз, вы можете просто захотеть вернуть bool,

def is_associative_cayley_table(table):
    if not is_cayley_table(table):
        return False

    for i in range (0,len(table)):
        for j in range (0,len(table)):
            for k in range (0,len(table)):
                if (table[table[i][j])][k])!=(table[i][(table[j][k])]):
                   return False
    return true

Кроме того, пока нет алгоритма для проверки ассоциативности множества.
Вы должны использовать грубую силу.

Лучшее, что вы можете сделать, это использовать тест ассоциативности Light, который не улучшает время выполнения худшего случая O(n^3), Это просто упрощает задачу в некоторых случаях.

Answer 2

Или с пониманием генератора в python:

      def is_associative(table, n):
    return all(table[x][table[a][y]] == table[table[x][a]][y] \
           for a in np.arange(n) for x in range(n) for y in range(n))

# calay table for ({0,1,...,n-1}, +n), addition modulo n, which is an Abelian group

n = 4
calay_table = np.zeros((n, n), dtype=int)
calay_table[0] = np.arange(n)
for i in range(1, n):
    calay_table[i] = np.roll(calay_table[i-1],-1)

print(calay_table)
# [[0 1 2 3]
# [1 2 3 0]
# [2 3 0 1]
# [3 0 1 2]]

is_associative(calay_table, n)
# True

У нас могли бы быть умные реализации теста ассоциативности Лайта .