algorithm - 随机生成关联操作

Question

在抽象代数中，a 的概念 group是相当基本的。要获得一个组，我们需要一组对象，以及一个 3 properties 的二元运算。 (如果算上关闭，则为 4)。如果我们想在给定有限集的情况下随机生成一个组(即随机生成一个 table 给出集合中所有可能的元素组合的结果)，那么很容易破解一个恒等元素，然后破解相反，但似乎很难随机生成关联的操作。

我的问题是是否有某种(有效的)方法可以随机生成关联运算。我试过随机生成一个操作，然后扰乱非关联关系，使它们一次关联一个，但这似乎并没有真正收敛。有什么想法吗？

Answer 1

这仅取决于什么被认为是“随机的”。一种选择是，不是随机生成实际的组操作矩阵，而是从一组已知通过构造关联的组中随机挑选一个关联组。

例如:

• 具有加法模 n 的整数群 {0...n-1} 是结合群
• 整数群{1..p-1}乘法模n是结合群当p是素数
• 如果 G 和 H 和两个结合群，则群操作 (g,h) * (g',h') = (g*g',h*h') 的群 (G,H) 是结合群
• 如果 G 是一个具有群运算 * 且 c 是 G 中的常量的群，则定义为 g @ g' = (g * c) * g' 的运算 @ 的结合性为 (g @ g') @ g'' = g * c * g' * c * g'' = g @ (g' @ g'')

因此，例如，为了生成大小为 N 的随机组，将 N 分解为素数 N = (p1, ..., pk)(同一个素数可以在该列表中出现多次)，然后从中构建随机乘积 q1, ..., qn 使得 N = q1 * ... * qn，然后对于每个 qi，选择一个加法或乘法整数组，添加随机常数，然后使用生成的乘积组作为一个随机的联合组。它不会生成所有具有相同概率的关联组，但它仍然是一个随机过程来获得随机加法组，并且可能比随机填充矩阵要好得多，尤其是当您需要更大的组时。