Terapia grupal: identificar grupos

17

Escriba un programa que determine si la tabla de multiplicación del magma finito dado representa un grupo. Un magma es un conjunto con una operación binaria que está cerrada, eso significa

  • para todo a, b en G, a * b está nuevamente en G (Cerrado)

Deje (G, *) ser un magma. (G, *) es un grupo si

  • para todos a, b, c en G, (a * b) * c = a * (b * c) (Asociatividad)
  • existe un elemento e en G tal que e * a = a * e = a para todo a en G (Existencia de elemento neutral)
  • para todo a en G hay ab en G tal que a * b = b * a = e donde e es el elemento neutral (Existencia de inversa)

Especificaciones

La entrada es de una cadena de n ^ 2-1 caracteres (un carácter para cada elemento del magma, permitido son 0-9, az) y solo representa la tabla leída fila por fila, omitiendo el nombre del operador. Puede suponer que la entrada representa un magma válido (eso significa que cada uno de los elementos aparece exactamente una vez en la fila / columna del encabezado).

Ejemplo: aquí tenemos la tabla de Z_4

+ | 0 1 2 3
-----------
0 | 0 1 2 3
1 | 1 2 3 0
2 | 2 3 0 1
3 | 3 0 1 2

La cadena de entrada será 012300123112302230133012. (O si usamos símbolos, también podría serlo nezdnnezdeezdnzzdneddnez). Tenga en cuenta que la secuencia de los elementos en la fila y en la columna no tiene que ser la misma, por lo que la tabla de Z_4 también podría verse así:

+ | 1 3 2 0
-----------
1 | 2 0 3 1
0 | 1 3 2 0
2 | 3 1 0 2
3 | 0 2 1 3

Esto también significa que el elemento neutral no está necesariamente en la primera columna o primera fila.

Si es un grupo, el programa debe devolver el carácter que representa el elemento neutral. Si no, tiene que devolver un valor falso (distinto de los valores 0-9 az)

Casos de prueba

Los no grupos pueden construirse fácilmente simplemente alterando un dígito de la cadena o alterando artificialmente las tablas que definen una operación que contradice uno de los axiomas del grupo.

Grupos

Trivial

* | x
-----
x | x

xxx

Neutral Element: x

H (grupo cuaternión)

* | p t d k g b n m 
-------------------
m | b d t g k p m n 
p | m k g d t n p b 
n | p t d k g b n m 
b | n g k t d m b p 
t | g m n p b k t d 
d | k n m b p g d t 
k | t b p m n d k g 
g | d p b n m t g k 

ptdkgbnmmbdtgkpmnpmkgdtnpbnptdkgbnmbngktdmbptgmnpbktddknmbpgdtktbpmndkggdpbnmtgk

Neutral Element: n

D_4

* | y r s t u v w x
-------------------
u | u x w v y t s r
v | v u x w r y t s
w | w v u x s r y t
x | x w v u t s r y
y | y r s t u v w x
r | r s t y v w x u
s | s t y r w x u v
t | t y r s x u v w


yrstuvwxuuxwvytsrvvuxwrytswwvuxsrytxxwvutsryyyrstuvwxrrstyvwxusstyrwxuvttyrsxuvw

Neutral Element: y

Z_6 x Z_2

x | 0 1 2 3 5 7 8 9 a b 4 6
---------------------------
0 | 0 1 2 3 5 7 8 9 a b 4 6 
1 | 1 2 3 4 0 8 9 a b 6 5 7 
2 | 2 3 4 5 1 9 a b 6 7 0 8 
7 | 7 8 9 a 6 2 3 4 5 0 b 1 
8 | 8 9 a b 7 3 4 5 0 1 6 2 
9 | 9 a b 6 8 4 5 0 1 2 7 3 
a | a b 6 7 9 5 0 1 2 3 8 4 
b | b 6 7 8 a 0 1 2 3 4 9 5 
3 | 3 4 5 0 2 a b 6 7 8 1 9 
4 | 4 5 0 1 3 b 6 7 8 9 2 a 
5 | 5 0 1 2 4 6 7 8 9 a 3 b 
6 | 6 7 8 9 b 1 2 3 4 5 a 0 

01235789ab46001235789ab4611234089ab6572234519ab67087789a623450b1889ab7345016299ab684501273aab6795012384bb678a0123495334502ab67819445013b67892a5501246789a3b66789b12345a0

Neutral Element: 0

A_4

* | i a b c d e f g h j k l
---------------------------
i | i a b c d e f g h j k l
a | a b i e c d g h f l j k
b | b i a d e c h f g k l j
c | c f j i g k a d l b e h
d | d h k b f l i e j a c g
e | e g l a h j b c k i d f
f | f j c k i g d l a h b e
g | g l e j a h c k b f i d
h | h k d l b f e j i g a c
j | j c f g k i l a d e h b
k | k d h f l b j i e c g a
l | l e g h j a k b c d f i

iabcdefghjkliiabcdefghjklaabiecdghfljkbbiadechfgkljccfjigkadlbehddhkbfliejacgeeglahjbckidfffjckigdlahbegglejahckbfidhhkdlbfejigacjjcfgkiladehbkkdhflbjiecgalleghjakbcdfi

Neutral Element: i

No grupos

Un bucle (Agrupa asociatividad faltante, o un Cuasi-Grupo con elemento neutral)

* | 1 2 3 4 5
-------------
1 | 1 2 3 4 5 
2 | 2 4 1 5 3 
3 | 3 5 4 2 1 
4 | 4 1 5 3 2 
5 | 5 3 2 1 4

12345112345224153335421441532553214

Neutral Element: 1
(2*2)*3 = 4*3 = 5 != 2 = 2*1 = 2*(2*3)

Un bucle de IP (de http://www.quasigroups.eu/contents/download/2008/16_2.pdf )

* | 1 2 3 4 5 6 7
-----------------
1 | 1 2 3 4 5 6 7
2 | 2 3 1 6 7 5 4
3 | 3 1 2 7 6 4 5
4 | 4 7 6 5 1 2 3
5 | 5 6 7 1 4 3 2
6 | 6 4 5 3 2 7 1
7 | 7 5 4 2 3 1 6

123456711234567223167543312764544765123556714326645327177542316

Neutral Element: 1
2*(2*4) = 2*6 = 5 != 7 = 3*4 = (2*2)*4

Monoide (por Quincunx, ¡gracias!)

Los monoides son magmas con asociatividad y un elemento neutral.

* | 0 1 2 3
-----------
0 | 0 1 2 3
1 | 1 3 1 3
2 | 2 1 0 3
3 | 3 3 3 3

012300123113132210333333

Neutral Element: 0

Otro monoide

(Multiplicación mod 10, sin el 5) Obviamente no tenemos inversos, y la asociatividad viene dada por el módulo de multiplicación 10.

* | 1 2 3 4 6 7 8 9
-------------------
1 | 1 2 3 4 6 7 8 9
2 | 2 4 6 8 2 4 6 8
3 | 3 6 9 2 8 1 4 7
4 | 4 8 2 6 4 8 2 6
6 | 6 2 8 4 6 2 8 4
7 | 7 4 1 8 2 9 6 3
8 | 8 6 4 2 8 6 4 2
9 | 9 8 7 6 4 3 2 1

Neutral Element: 1   12346789112346789224682468336928147448264826662846284774182963886428642998764321
falla
fuente
Pensé en agregar otra tabla, mucho más grande, solo por diversión: ideone.com/823aRG
Justin
Solo por diversión, aquí hay otro muy grande que rompe la 0-9a-zregla: ideone.com/vC0ewt
Justin
Para alguien que no sabe nada sobre grupos, magmas, etc., las especificaciones son confusas. Por ejemplo, ¿las operaciones son conmutativas? (entonces la tabla es redundante). Además. la posición de neutral en la primera fila no está relacionada con tener el mismo orden en fila y columna: con 10101010el orden es el mismo y el neutral está en la última fila y columna
edc65
@edc Los grupos no son necesariamente conmutativos (los grupos conmutativos se denominan abelianos). La definición del grupo a está completa (es la definición habitual), cualquier cosa adicional proporcionaría una restricción adicional. En esas tablas, la multiplicación con el elemento neutral generalmente está en la primera fila / columna, y la secuencia de los elementos de la fila / columna de encabezado suele ser la misma, pero aún puede escribir una tabla válida sin seguir esas convenciones, que es lo que quería incluir aquí.
flawr
1
Eliminé algunos comentarios que parecían obsoletos. Por favor notifíqueme de cualquier comentario que deba ser recuperado.
Martin Ender

Respuestas:

4

Octava, 298 290 270 265 caracteres

function e=g(s)
c=@sortrows;d=a=c(c(reshape(a=[0 s],b=numel(a)^.5,b)')');
for i=2:b a(a==a(i))=i-1;end;
a=a(2:b,2:b--);u=1:b;
e=(isscalar(e=find(all(a==u')))&&a(e,:)==u&&sum(t=a==e)==1&&t==t')*e;
for x=u for y=u for z=u e*=a(a(x,y),z)==a(x,a(y,z));end;end;end;e=d(e+1);

265: Se eliminó el asa de función innecesaria.

270: Después de todo, la verificación de que e==hpara e siempre satisfactoria e · a = a y h siempre satisfactoria a · h = a no era necesaria. Esto no es posible para que sean diferentes ( e · h =? ).

Los detalles de la explicación de la solución a continuación siguen siendo relevantes.


290:

function e=g(s)
c=@sortrows;d=a=c(c(reshape(a=[0 s],b=numel(a)^.5,b)')');
for i=2:b a(a==a(i))=i-1;end;
a=a(2:b,2:b--);u=1:b;
s=@isscalar;e=(s(e=find(all(a==u')))&&s(h=find(all(a'==u')'))&&sum(t=a==e)==1&&t==t')*e;
for x=u for y=u for z=u e*=a(a(x,y),z)==a(x,a(y,z));end;end;end;e=d(e+1);

La primera línea

c=@sortrows;d=a=c(c(reshape(a=[0 s],b=numel(a)^.5,b)')'); simplemente almacena la entrada en la tabla nxn (con cero caracteres en el lugar de la marca de operación), y luego ordena lexicográficamente columnas y filas, para que las filas y columnas reciban el mismo orden:

+ | z a t b                        + | a b t z
-----------                        -----------
z | t b a z         becomes        a | t a z b
b | z a t b      ============>     b | a b t z
t | a z b t                        t | z t b a
a | b t z a                        z | b z a t

Ahora, vuelvo a asignar "a","b","t","z"al estándar 1, 2, 3, 4, para poder indexar la tabla de manera eficiente. Esto se hace por la línea for i=2:b a(a==a(i))=i-1;end;. Produce tabla como

0   1   2   3   4
1   3   1   4   2
2   1   2   3   4
3   4   3   2   1
4   2   4   1   3

, donde podemos deshacernos de la primera fila y columna con a=a(2:b,2:b--);u=1:b;:

3  1  4  2
1  2  3  4
4  3  2  1
2  4  1  3

Esta tabla tiene las propiedades dadas:

  • si el elemento neutral e existe, exactamente una ( isscalar) fila y una columna tienen el valor de vector de fila u=[1 2 3 ... number-of-elements]:

s=@isscalar;e=(s(e=find(all(a==u')))&&s(h=find(all(a'==u')'))&&...

  • si cada elemento a tiene un elemento inverso a ' , se mantienen dos cosas: el elemento neutro e aparece solo una vez en cada columna y solo una vez en cada fila ( sum(t=a==e)==1) y, para satisfacer a' · a = a · a ' , las ocurrencias de e son simétrico con respecto a la traducciónt==t'

  • a · b se puede recuperar mediante una t(a,b)indexación simple . Luego verificamos la asociatividad en el ciclo aburrido:

for x=u for y=u for z=u e*=a(a(x,y),z)==a(x,a(y,z));end;end;end;

La función devuelve el elemento neutral de la forma en que apareció en la tabla original ( e=d(e+1)) o el carácter nulo si la tabla no describe un grupo.

pawel.boczarski
fuente
2
Bien hecho y bien explicado. Debería devolver el elemento neutral en lugar de 1.
edc65
Corregido, ahora devuelve el valor adecuado.
pawel.boczarski
1
OCTAVE FTW =) No estoy seguro acerca de dos cosas (provenientes de matlab), pero quizás pueda usarlo para mejorar su respuesta: ¿Podría `a (f (a == a (i))) = i-1` reducirse a a(a==a(i))=i-1? Aparte de eso, quizás pueda usar en (...)^.5lugar de sqrt(...).
flawr
@flawr Gracias, ambos funcionan en octava (versión 3.8.1).
pawel.boczarski
6

Rubí, 401 ... 272

f=->s{n=(s.size+1)**0.5
w=n.to_i-1
e=s[0,w].split''
s=s[w,n*n]
m={}
w.times{(1..w).each{|i|m[s[0]+e[i-1]]=s[i]}
s=s[n,n*n]}
s=e.find{|a|e.all?{|b|x=m[a+b]
x==m[b+a]&&x==b}}
e.all?{|a|t=!0
e.all?{|b|x=m[a+b]
t||=x==m[b+a]&&x==s
e.all?{|c|m[m[a+b]+c]==m[a+m[b+c]]}}&&t}&&s}

Este es mi primer programa ruby! Esto define una función lambda que podemos probar haciendo puts f[gets.chomp]. Regreso falsepor mi valor falso. La primera mitad de la función simplemente analiza la entrada en un mapa, luego la segunda mitad verifica las posibilidades.

f=->s{
    n=((s.size+1)**0.5).to_i
    w=n-1
    e=s[0,w].split'' # create an array of elements of the potential group
    s=s[w,n*n]
    m={} # this map is what defines our operation
    w.times{
        (1..w).each{               # for each element in the row of the table
            |i|m[s[0]+e[i-1]]=s[i] # put the value into the map
        }
        s=s[n,n*n]
    }
    s=e.find{|a| # s is the identity
        e.all?{|b|
            x=m[a+b]
            x==m[b+a]&&x==b # is a the identity?
        }
    }
    e.all?{|a| # implicit return statement
        t = !0 # t = false
        e.all?{|b| # check for inverses
            x=m[a+b]
            t ||= x==m[b+a]&&x==s # t is now true if b was a's inverse
            e.all?{|c|
                m[m[a+b]+c]==m[a+m[b+c]] # check associativity
            }
        } && t
    }&&s
}
Justin
fuente
55
¡Bienvenido a las maravillas del golf en Ruby! ;) niles un valor falso más corto que false. Las funciones se pueden definir como lambdas q=->{abort'false'}(si toman parámetros, utilícelos []para llamarlos en lugar de ()). Creo .charsque ya debería darle una matriz, por lo que no es necesario .to_a. Si no necesita una nueva línea final, $><<es un byte más corto que el putsespacio más. Hash.newno necesita los paréntesis. Eso es todo lo que puedo ver por ahora. ¡Seguid así! ;)
Martin Ender
La charscosa es extraña. ¿Qué versión de Ruby estás usando?
Martin Ender
@ MartinBüttner 1.9.3
Justin
Ah, claro, he estado mirando la documentación de 2.1.5.
Martin Ender el
1
Se puede reemplazar Math.sqrt(...)con ...**0.5. Además, a if bse puede reescribir: b&&apara evitar los dos espacios
Cristian Lupascu
4

JavaScript (ES6) 285 243 278

Ejecute el fragmento para probar (siendo ES6 solo funciona en Firefox)

Editar 2 Corrección de errores. Me equivoqué al encontrar el elemento neutral, comprobando solo de una manera. (¡Necesito mejores casos de prueba!)

Editar Utilizando una concatenación de cadenas más simple en lugar de un índice doble (como @Quincunx), no sé lo que estaba pensando. Además, la verificación inversa simplificada, aún debería funcionar.

F=t=>(
  e=t.slice(0,d=Math.sqrt(t.length)|0),
  t=t.slice(d).match('.'.repeat(d+1),'g'),
  t.map(r=>{
    for(v=r[i=0],
        j=e.search(v)+1, // column for current row  element
        r!=v+e|t.some(r=>r[j]!=r[0])?0:n=v; // find neutral
        c=r[++i];
       )h[v+e[i-1]]=c
  },h={},n=''),
  e=[...e],!e.some(a=>e.some(b=>(
    h[a+b]==n&&--d, // inverse
    e.some(c=>h[h[a+b]+c]!=h[a+h[b+c]]) // associativity
  )
  ))&&!d&&n
)
input { width: 400px; font-size:10px }
Click on textbox to test - Result : <span id=O></span><br>
<input value='...' onclick='O.innerHTML=F(this.value)'> (?)
<br>Groups<br>
<input value='nezdnnezdeezdnzzdneddnez' onclick='O.innerHTML=F(this.value)'> (n)<br>
<input value='ptdkgbnmmbdtgkpmnpmkgdtnpbnptdkgbnmbngktdmbptgmnpbktddknmbpgdtktbpmndkggdpbnmtgk' onclick='O.innerHTML=F(this.value)'> (n)<br>
<input value='yrstuvwxuuxwvytsrvvuxwrytswwvuxsrytxxwvutsryyyrstuvwxrrstyvwxusstyrwxuvttyrsxuvw' onclick='O.innerHTML=F(this.value)'> (y)<br>
<input value='01235789ab46001235789ab4611234089ab6572234519ab67087789a623450b1889ab7345016299ab684501273aab6795012384bb678a0123495334502ab67819445013b67892a5501246789a3b66789b12345a0'onclick='O.innerHTML=F(this.value)'> (0)<br>
Non groups <br>
<input value='12345112345224153335421441532553214' onclick='O.innerHTML=F(this.value)'> (FAIL)<br>
<input value='123456711234567223167543312764544765123556714326645327177542316' onclick='O.innerHTML=F(this.value)'> (FAIL)<br>
<input value='012300123113132210333333' onclick='O.innerHTML=F(this.value)'> (FAIL)<br>

edc65
fuente
2

Haskell 391B

import Data.Maybe
import Data.List
o a b=elemIndex b a
l£a=fromJust.o a$l
a§b=[a!!i|i<-b]
f s|isJust j&&and(map(isJust.o h)s)&&and[or[p%q==e|q<-h]&&and[p%(q%r)==(p%q)%r|q<-h,r<-h]|p<-h]=[e]|True="!"where n=floor$(sqrt(fromIntegral$length s+1))-1;h=take n s;g=[s§[a..b]|(a,b)<-zip[1+n,2+n+n..][n+n,3*n+1..(n+1)^2]];v=s§[n,1+2*n..n+n*n];a%b=g!!(b£v)!!(a£h);j=o g h;e=v!!fromJust j

¡Maldice esos imports!

import Data.Maybe
import Data.List

{- rename elemIndex to save characters -}
o a b=elemIndex b a

{- get the index of l in a -}
l£a=fromJust.o a$l

{- extract a sublist of a with indices b -}
a§b=[a!!i|i<-b]

f s |isJust j {-Identity-}
     &&and (map (isJust.o h) s) {-Closure-}
     &&and[
        or [p%q==e|q<-h] {-Inverse-}
        && and [ p%(q%r)==(p%q)%r | q<-h,r<-h ] {-Associativity-}
     |
        p<-h
     ]=[e]
    |True="!"
    where
    {-size-}    n=floor$(sqrt(fromIntegral$length s+1))-1
    {-horiz-}   h=take n s
    {-table-}   g=[s§[a..b]|(a,b)<-zip[1+n,2+n+n..][n+n,3*n+1..(n+1)^2]]
    {-vert-}    v=s§[n,1+2*n..n+n*n]
    {-operate-} a%b=g!!(b£v)!!(a£h)
                j=o g h {-index of the first row identical to the top-}
    {-ident-}   e=v!!fromJust j

Explicación

f::String->Stringasigna la cadena a cualquiera e::Char, el elemento de identidad o !.

La wherecláusula crea un montón de variables y funciones, que he comentado; v::[Int]es la lista vertical de elementos, h::[Int]la horizontal.

%::Char->Char->Char aplica la operación de grupo a sus argumentos.

g::[[Int]]es la tabla de grupo (para desreferenciar usando %)

j::Maybe Intcontiene el índice de la identidad en vsi existe, de lo contrario Nothing, por eso isJust jes la condición fpara la identidad.

alexander-brett
fuente
¿Puedes explicar un poco lo que está pasando aquí?
xebtl
He agregado algunos comentarios, pero la esencia básica es 'aplicar las pruebas a la tabla de grupo'. Tenga en cuenta que {- -}es un comentario. ¿Tiene alguna pregunta más específica o eso lo aclara?
alexander-brett
Gracias. Supongo que para entenderlo realmente tendría que aprender algo de Haskell primero :-)
xebtl