标签: finite-group-theory

我有一个优化问题,我想知道是否有一个聪明的方法来解决它.(这可能已经被广泛研究过,我只是不知道要查找它的名称.)

我有一个(编辑:免费)有限生成的阿贝尔群G,在n发电机上.我还有一组P元素G,每个元素都标有严格正数的成本.所有的生成器都G出现在P,因此总是可以表达G作为元素P或其反转的产物的任何元素.任何此类产品的成本是P其中出现的元素的成本之和,并考虑它们出现的频率.表示身份元素的nullary产品的成本G为零.

考虑到该组的一个元素,我想找到一种方法来找到一个最低成本的产品,用它的元素来表达它P.

将其转换为最短路径问题是没有负面的自行车(在无限图上,但对于任何给定的元素,您只需要在标识元素附近的有限部分).将它转换为整数线性编程问题也很简单.

可能是其中一种翻译是要走的路？或者此问题的其他结构是否导致更容易的方法呢？在我的实际问题5 <= n <= 10和我感兴趣的元素中,从来没有大于+/- 20的任何发生器的多重性.

我在Haskell工作,因此功能方法优先于有状态方法,但有状态方法也可以.

你如何编写Python代码来检查是否运行？在由 Cayley 表定义的集合 {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

题

如何实现运行长度编码模数n>=1？因为n=4，考虑到输入AAABBBBABCCCCBBBDAAA，我们想要一个输出[('D', 1), ('A', 3)]。注意由于模数运算导致的长距离合并。见说明。

解释

中第一次出现BBBB编码到(B, 4)其modulus 4是(B, 0)，从而消除本身进行。参见图表（忽略空格；它们仅用于说明目的）：

AAABBBBABCCCCBBBDAAA
A3  B4 ABCCCCBBBDAAA
A3  B0 ABCCCCBBBDAAA
A3     ABCCCCBBBDAAA
A4      BCCCCBBBDAAA
A0      BCCCCBBBDAAA
        BCCCCBBBDAAA
        ... 
                DA3

一个更简单的例子，当没有合并发生时，因为没有被取消modulus 4：输入AAABABBBC产生输出[('A',3),('B',1),('A',1),('B',3),('C',1)]。

要求

• Haskell 实现是首选，但也欢迎其他实现！
• 比 3rd 方库更喜欢标准/公共库函数。
• 首选使用高阶函数的可读和简洁的程序。
• 优先考虑效率（在不必要时不要遍历整个列表）

我的程序

我在 Haskell 中实现了这个，但它看起来太冗长而且读起来很糟糕。关键思想是一次检查三个元组，如果我们既不能取消0元组也不能在手头的三个元组中合并一对元组，则只向前推进一个元组。

import Data.List (group)

test = [('A', 1), ('A', 2), ('B', 2), ('B', …

这是一个由两部分组成的问题，但第二部分依赖于第一部分。

出于教育目的，我试图为组实现一个抽象基类和测试套件（抽象代数的概念）。代数群定义的一部分相当于类型约束，我想在 ABC 上实现该类型约束，并且如果具体类上的方法不符合该约束，则会有一些抱怨。

我已经为逻辑下的布尔值组实现了第一遍实现and，但它至少有两个问题，我希望你能帮助我修复它。

from __future__ import annotations
from abc import ABC, abstractmethod


class AbsGroup(ABC):
    @abstractmethod
    def op(self, other: AbsGroup) -> AbsGroup:   # <-- Line-of-interest #1
        pass


class Bool(AbsGroup):

    def __init__(self, val="False"):

        if val not in ["True", "False"]:
            raise ValueError("Invalid Bool value %s" % val)

        self.val = val

    def op(self, other):
        """Logical AND"""
        if self.val == "True" and other.val == "True":  # <-- Line-of-interest #2
            return Bool("True")
        return Bool("False")

    def __eq__(self, other):
        return self.val == …

我刚刚在维基百科上读到了与位字段有关的基本阿贝尔群.如果有人能够解释我这个特定的段落,我会努力完全掌握位字段,我将不胜感激.