随机产生关联操作，

在抽象代数，一个group的概念是相当基本的。为了得到一个组，我们需要一组对象，并且使用3 properties（如果您计算关闭，则为4）执行二进制操作。如果我们想随机生成一个给定有限集合的组（也就是说，随机生成一个给出集合中每个可能组合元素的结果的集合），那么在身份元素中进行攻击并且反向攻击非常容易，但似乎很难随机生成一个关联的操作。随机产生关联操作，

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

来源

2011-11-10 deontologician

我会尝试在http://math.stackexchange.com/ –

我怎样才能移动它有这个问题？ – deontologician

我认为你不能，但如果你决定这样做，你可以在那里重新发布。 –

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

例如：

整数组{0 ... N-1}的加法模n是一个缔合基团
组整数{1..p-1}与乘法模的n是一个缔合基团，当p是素数
如果G和H和两个缔合基团，则基团（G，H）同组操作（G，H）*（G 'H'）=（G * G 'H * 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-10 20:16:06

您可能也会觉得这很有用：http://en.wikipedia.org/wiki/Classification_of_finite_simple_groups 然后，您可以将组合分解为有限简单组的组合。 –

特别是你也需要这个结果：“一个不简单的组可以分成两个更小的组，一个正常的子组和商组，并且该过程可以重复。” （从这里http://en.wikipedia.org/wiki/Simple_group） –

二进制操作的结合性为三元组（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-10 19:42:02 Patrick87

你可以试试Knuth-Bendix完成。

在本质上，这意味着您强制组通过反复识别关联方程的双方是关联的。

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

来源

2011-11-11 08:08:25 starblue

你介意扩展你的文章，也许有一个简单的例子吗？ – deontologician

如果你发现关联性的两边给出了两个不同的元素'x'和'y'，那么你就可以识别它们，那就是你用'x'替换'y'并摆脱'y'。您还需要通过确定它们的总和和反转来考虑连锁反应。 – starblue

这里有一些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-12 23:50:48

随机产生关联操作，

回答

相关问题