4

在抽象代数中，群的概念是相当基础的。要获得一个组，我们需要一组对象和一个具有3 个属性的二元运算（如果算上闭包，则为 4 个）。如果我们想在给定有限集合的情况下随机生成一个组（即随机生成一个表格，给出集合中每个可能的元素组合的结果），那么很容易破解一个单位元素，并破解逆，但似乎很难随机生成一个关联的操作。

我的问题是是否有一些（有效的）方法可以随机生成关联操作。我尝试随机生成一个操作，然后扰乱非关联关系，以便它们一次关联一个，但这似乎并没有真正收敛。有任何想法吗？

4

4 回答 4

3

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

例如：

  • 具有加法模 n 的整数组 {0...n-1} 是结合组
  • 当 p 为素数时，模数为 n 的整数组 {1..p-1} 是结合群
  • 如果 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，选择一个加法或乘法整数组，添加随机常数，然后将所得乘积组用作随机关联团体。它不会生成具有相同概率的所有关联组，但它仍然是获得随机加法组的随机过程，并且可能比随机填充矩阵要好得多，特别是如果您需要更大的组。

于 2011-11-10T20:16:06.037 回答
3

您可以尝试 Knuth-Bendix 补全。

从本质上讲，这意味着您通过重复识别关联方程的两侧来强制您的组具有关联性。

因此，您的组将变得小于初始大小，但您可以再次添加一些元素并继续。

于 2011-11-11T08:08:25.887 回答
1

对于三元组 (a, b, c)，二元运算的结合性定义为 (a * (b * c)) = ((a * b) * c)。因此，当您随机定义 a * b 时，您可以简单地随机选择一个不会导致违反关联性的 a * b 分配；如果没有任何此类分配，请备份并在最后一步选择其他分配。所以...

  MakeRandomAssociative(table[1..N, 1..N], elements[1..N], n)
  0. if n = N + 1 return true
  1. a := elements[n mod N]
  2. b := elements[n // N]
  3. candidates = []
  4. for each c in elements do
  5.    table[n mod N,n // N] = c
  6.    if not violates_associativity(table) then candidates.add(c)
  7. if empty(candidates) return false
  8. else then
  9.    c := remove_random(candidates)
  A.    table[n mod N,n // N] = c
  B.    if MakeRandomAssociative(table, elements, n+1) then
  C.       return true
  D.    else goto 7

这是丑陋和蛮力，但是（这里给出的实现可能是错误的）它应该在概念上找到一个在某种意义上应该是“随机”的关联运算符。

于 2011-11-10T19:42:02.357 回答
1

以下是一些 Prolog 谓词，它们在给定集合上生成所有二进制函数：

gen_binop(A,BinOp):-
    cartesian(A,Cart),
    gen_func(Cart,A,BinOp).gen_func(Dom,Rng,Func) :-
    is_set(Dom),
    is_set(Rng),
    gen_func(Dom,Rng,[],Tmp),
    reverse(Tmp,Func).

cartesian(A,B,Cart):-
    findall([X,Y],(member(X,A),member(Y,B)),L),
    list_to_set(L,Cart),!.

gen_func([],_,Func,Func).
gen_func([H|T],Rng,Func1,Func) :-
    member(Y,Rng),
    Func2=[[H,Y]|Func1],
    gen_func(T,Rng,Func2,Func).

Finally, we test to see if any given binary operation is non-associative (and then negate that to find the associative ones):

non_assoc_binop(BinOp):-
    domain(BinOp,D),
    flatten(D,A),
    cartesian3(A,A,A,Cart),
    member([X,Y,Z],Cart),
    eval(BinOp,[X,Y],X1),
    eval(BinOp,[Y,Z],Y2),
    eval(BinOp,[X1,Z],U),
    eval(BinOp,[X,Y2],V),
    U\=V.

eval(F,X,Y) :-
    function(F),
    member([X,Y],F).

function(PL) :-
    pair_list(PL),
    forall(image(PL,_,ImgX),func_image(PL,ImgX)).

image(PL,X,ImgX) :-
    pair_list(PL),
    domain(PL,Dom),
    member(X,Dom),
    findall(Y,member([X,Y],PL),L),
    list_to_set(L,ImgX).

func_image(PL,ImgX) :-
    image(PL,_,ImgX),
    length(ImgX,1).

pair_list([]).
pair_list([[_,_]|T]) :-
    pair_list(T).
于 2012-03-12T23:50:48.120 回答