群论和Python

Question

如何编写 Python 代码来检查 Cayley table 定义的集合 {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 次，您可能只想 return 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's Associativity Test，"does not improve the worst case runtime of O(n^3). It just simplifies the task in some cases."

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

我们可以巧妙地实现 Light's Associativity Test。

群论和Python

Group theory and Python

python

python-3.x

math

abstract-algebra

finite-group-theory