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
fuente
0-9a-z
regla: ideone.com/vC0ewt10101010
el orden es el mismo y el neutral está en la última fila y columnaRespuestas:
Octava,
298 290 270265 caracteres265: Se eliminó el asa de función innecesaria.
270: Después de todo, la verificación de que
e==h
para 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:
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:Ahora, vuelvo a asignar
"a","b","t","z"
al estándar1, 2, 3, 4
, para poder indexar la tabla de manera eficiente. Esto se hace por la líneafor i=2:b a(a==a(i))=i-1;end;
. Produce tabla como, donde podemos deshacernos de la primera fila y columna con
a=a(2:b,2:b--);u=1:b;
:Esta tabla tiene las propiedades dadas:
isscalar
) fila y una columna tienen el valor de vector de filau=[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.fuente
a(a==a(i))=i-1
? Aparte de eso, quizás pueda usar en(...)^.5
lugar desqrt(...)
.Rubí,
401... 272Este es mi primer programa ruby! Esto define una función lambda que podemos probar haciendo
puts f[gets.chomp]
. Regresofalse
por mi valor falso. La primera mitad de la función simplemente analiza la entrada en un mapa, luego la segunda mitad verifica las posibilidades.fuente
nil
es un valor falso más corto quefalse
. Las funciones se pueden definir como lambdasq=->{abort'false'}
(si toman parámetros, utilícelos[]
para llamarlos en lugar de()
). Creo.chars
que 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 elputs
espacio más.Hash.new
no necesita los paréntesis. Eso es todo lo que puedo ver por ahora. ¡Seguid así! ;)chars
cosa es extraña. ¿Qué versión de Ruby estás usando?Math.sqrt(...)
con...**0.5
. Además,a if b
se puede reescribir:b&&a
para evitar los dos espaciosJavaScript (ES6) 285
243 278Ejecute 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.
fuente
Haskell 391B
¡Maldice esos
import
s!Explicación
f::String->String
asigna la cadena a cualquierae::Char
, el elemento de identidad o!
.La
where
clá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 Int
contiene el índice de la identidad env
si existe, de lo contrarioNothing
, por esoisJust j
es la condiciónf
para la identidad.fuente
{- -}
es un comentario. ¿Tiene alguna pregunta más específica o eso lo aclara?