Случайно генерирующие ассоциативные операции

Question

В абстрактной алгебре понятие группы является довольно фундаментальным. Чтобы получить группу, нам нужен набор объектов и бинарная операция с 3 свойствами (4, если вы считаете замыкание). Если мы хотим случайным образом сгенерировать группу с заданным конечным набором (то есть случайным образом сгенерировать таблицу , дающую результат каждой возможной комбинации элементов в наборе), то довольно легко взломать тождество элемент, и взломать в обратном порядке, но кажется очень трудно случайным образом генерировать ассоциативную операцию.

Мой вопрос заключается в том, существует ли какой-либо (эффективный) способ случайной генерации ассоциативной операции. Я попытался случайным образом сгенерировать операцию, а затем нарушить неассоциативные отношения, чтобы они были ассоциативными по одному, но, похоже, это не сходится. Есть идеи?

Answer 1

Это зависит только от того, что считается «случайным».Один из вариантов состоит в том, чтобы вместо генерации фактической матрицы групповых операций случайным образом случайным образом выбирать ассоциативную группу из семейства групп, которые, как известно, являются ассоциативными по построению.

Например:

• Группа целых чисел {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 ', ассоциативнаas (g @ g ') @ g' '= g * c * g' * c * g '' = g @ (g '@ g' ')

Так, например, вчтобы сгенерировать случайную группу размера N, получить факторизацию N на простые числа N = (p1, ..., pk) (одно и то же простое число может появляться несколько раз в этом списке), затем построить случайные произведения q1, ...,дпиз них так, чтобы N = q1 * ... * qn, а затем для каждого qi выберите аддитивную или мультипликативную целочисленную группу, добавьте случайные константы, а затем используйте полученную группу продуктов в качестве случайной ассоциативной группы.Он не будет генерировать все ассоциативные группы с одинаковыми вероятностями, но это все равно случайный процесс получения случайной аддитивной группы, и он может быть намного лучше, чем случайное заполнение матрицы, особенно если вам нужны большие группы.

Answer 2

Вы можете попробовать завершение Кнут-Бендикс.

По сути это означает, что вы заставляете свою группу быть ассоциативной, многократно идентифицируя две стороны уравнения ассоциативности.

Таким образом, ваша группа станет меньше вашего первоначального размера, но вы можете снова добавить некоторые элементы и продолжить.

Answer 3

Вот некоторые предикаты 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).

Answer 4

Ассоциативность бинарных операций определяется для троек (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

Это уродливо и грубо, но (приведенная здесь реализация может быть ошибочной) концептуально должен найти ассоциативный оператор, который в некотором смысле должен быть "случайным".