16

Una matriz de signos alternos es una matriz nby ncompuesta por los números -1, 0, 1, de modo que:

La suma de cada fila y columna es 1
Las entradas distintas de cero en cada fila y columna se alternan en el signo

Estas matrices generalizan las matrices de permutación, y el número de tales matrices para un dado nfue de interés durante algún tiempo. Ocurren naturalmente durante el método de condensación Dodgson para calcular los determinantes de la matriz (llamado así por Charles Dodgson, mejor conocido como Lewis Carroll).

Aquí hay algunos ejemplos de matrices de signos alternos de 4 por 4:

 0  1  0  0          1  0  0  0          0  0  1  0          0  0  1  0    
 0  0  1  0          0  0  1  0          0  1 -1  1          1  0 -1  1
 1  0  0  0          0  1 -1  1          1 -1  1  0          0  1  0  0
 0  0  0  1          0  0  1  0          0  1  0  0          0  0  1  0

Y aquí hay algunos ejemplos de matrices de 4 por 4 que no son matrices de signos alternos:

 0  1  0  0
 0  0  0  1
 1  0  0  0
 0  0  1 -1    (last row and last column don't add to 1)

 0  0  0  1
 1  0  0  0
-1  1  1  0
 1  0  0  0    (third row does not alternate correctly)

Su programa o función se les dará una npor nmatriz ( n >= 1) de -1S, 0s y 1s - salida un valor Truthy si la matriz dada es una matriz de señal alterna, de lo contrario la salida un valor Falsy.

Este es el código de golf , por lo que el objetivo es minimizar el número de bytes utilizados.

Casos de prueba

Los siguientes casos de prueba se dan en un formato de lista 2D similar a Python.

Verdad:

[[1]]
[[1,0],[0,1]]
[[0,1],[1,0]]
[[0,1,0],[0,0,1],[1,0,0]]
[[0,1,0],[1,-1,1],[0,1,0]]
[[0,1,0,0],[0,0,1,0],[1,0,0,0],[0,0,0,1]]
[[1,0,0,0],[0,0,1,0],[0,1,-1,1],[0,0,1,0]]
[[0,0,1,0],[0,1,-1,1],[1,-1,1,0],[0,1,0,0]]
[[0,0,1,0],[1,0,-1,1],[0,1,0,0],[0,0,1,0]]
[[0,0,1,0,0],[0,1,-1,1,0],[1,-1,1,0,0],[0,1,0,-1,1],[0,0,0,1,0]]
[[0,0,1,0,0,0,0,0],[1,0,-1,0,1,0,0,0],[0,0,0,1,-1,0,0,1],[0,0,1,-1,1,0,0,0],[0,0,0,0,0,0,1,0],[0,0,0,0,0,1,0,0],[0,1,-1,1,0,0,0,0],[0,0,1,0,0,0,0,0]]
[[0,0,0,0,1,0,0,0],[0,0,1,0,-1,1,0,0],[0,0,0,1,0,0,0,0],[1,0,0,-1,1,-1,1,0],[0,1,-1,1,-1,1,0,0],[0,0,0,0,1,0,0,0],[0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1]]

Falsy

[[0]]
[[-1]]
[[1,0],[0,0]]
[[0,0],[0,1]]
[[-1,1],[1,0]]
[[0,1],[1,-1]]
[[0,0,0],[0,0,0],[0,0,0]]
[[0,1,0],[1,0,1],[0,1,0]]
[[-1,1,1],[1,-1,1],[1,1,-1]]
[[0,0,1],[1,0,0],[0,1,-1]]
[[0,1,0,0],[0,0,0,1],[1,0,0,0],[0,0,1,-1]]
[[0,0,1,0],[0,0,1,0],[1,0,-1,1],[0,1,0,0]]
[[0,0,0,1],[1,0,0,0],[-1,1,1,0],[1,0,0,0]]
[[1,0,1,0,-1],[0,1,0,0,0],[0,0,0,0,1],[0,0,0,1,0],[0,0,0,0,1]]
[[0,0,1,0,0],[0,1,-1,1,0],[1,-1,1,0,0],[0,1,1,-1,0],[0,0,-1,1,1]]
[[0,-1,0,1,1],[1,-1,1,-1,1],[0,1,1,0,-1],[1,1,-1,1,-1],[-1,1,0,0,1]]
[[0,0,1,0,0,0,0,0],[1,0,1,0,1,0,0,0],[0,0,0,1,-1,0,0,1],[0,0,1,-1,1,0,0,0],[0,0,0,0,0,0,1,0],[0,0,0,0,0,1,0,0],[0,1,-1,1,0,0,0,0],[0,0,1,0,0,0,0,0]]

code-golf array-manipulation decision-problem matrix Sp3000
fuente

1

Relacionado

Peter Taylor

3

Retina , 62 58 56 53 bytes

El recuento de bytes asume la codificación ISO 8859-1, y \tdebería reemplazarse por pestañas reales (0x09 que, de lo contrario, SE convertiría en espacios).

$
\t$`¶
O$#`...(?<=^[^\t]*(.+))
$.1
T` 0
^(1(-11)*\s)+$

El formato de entrada es una matriz donde cada columna usa tres caracteres alineados a la derecha, por ejemplo:

El resultado es 0(falso) o 1(verdadero).

Banco de pruebas. (Las primeras líneas transforman el formato de entrada y permiten que Retina ejecute varios casos de prueba a la vez).

Explicación

Afortunadamente, la entrada es una matriz cuadrada: la transposición de cuadrados es casi factible en Retina, mientras que la transposición de rectángulos es un dolor enorme.

$
\t$`¶

Comenzamos agregando una pestaña, toda la entrada nuevamente (usando el prefijo $`) y luego un salto de línea al final (usando el alias de Retina ¶). Estamos usando una pestaña para separar las dos copias para poder distinguir entre ellas cuando estamos transponiendo una de ellas, y al usar un carácter de espacio en blanco podemos guardar un par de bytes más adelante.

O$#`...(?<=^[^\t]*(.+))
$.1

Este es el bit más complicado: transponer la primera copia de la matriz. La idea es hacer coincidir las celdas en la primera copia y luego ordenarlas (de manera estable) por la posición horizontal. Emparejamos las celdas con ...(ya que siempre tienen tres caracteres de ancho) y luego medimos la posición horizontal con el (.+)interior del reverso. Luego, para asegurarnos de que solo transponemos la primera copia, verificamos que podemos llegar al principio de la cadena sin pasar de una pestaña.

Puede notar que esto también coincidirá con algunas cadenas de tres bytes (que ni siquiera se alinean con las celdas) en la primera fila de la segunda copia, ya que .+pueden pasar a través de la pestaña. Sin embargo, esto no es un problema porque la posición horizontal de estas coincidencias es estrictamente mayor que cualquiera dentro de la primera copia, por lo que estas coincidencias permanecen en su posición.

El resto es bastante simple:

T` 0

Eliminamos espacios y ceros de la entrada.

^(1(-11)*\s)+$

Y finalmente verificamos que toda la entrada consiste en filas de la forma terminadas en espacios en blanco 1(-11)*, es decir, una secuencia alterna de 1y -1que comienza y termina con 1(porque de lo contrario no se suma a 1).

Martin Ender
fuente

3

Jalea, 15 bytes

;Zḟ€0;€-;@€-IFP

Pruébalo en línea!

;Zḟ€0;€-;@€-IFP   Main monadic chain. Argument: z

;Z                Concatenate with its transpose.
  ḟ€0             Remove zeros from each sub-list. At this point,
                  one expects lists of the form [1, -1, 1, -1, ..., 1] for truthy,
                  and any other arrays containing purely 1 and -1 for falsey.
     ;€-          Append -1 to each sub-list.
        ;€@-      Prepend -1 to each sub-list.
            I     Compute the difference between each term. At this point,
                  for truthy, one expects arrays filled with 2, and arrays
                  containing 0 otherwise.
             FP   Product of every item. This checks if any item is equal to zero.

Monja permeable
fuente

3

Pyth, 16 bytes

!sm-sM._+d_1U2+C

Pruébelo en línea: Demostración o conjunto de pruebas

Explicación:

!sm-sM._+d_1U2+CQQ   two implicit Qs (=input matrix) at the end
              +CQQ   zip Q and connect it with Q (=list of columns and rows)
  m                  map each column/row d to:
        +d_1            append -1 to d
      ._                compute all prefixes of ^
    sM                  compute the sums of the prefixes
   -        U2          remove zeros and ones
                        a column/row is correct, if this gives an empty list 
 s                   connect up all resulting lists
!                    check, if this result is empty

Jakube
fuente

3

Jalea , 11 bytes

;Zj-+\ṚQḄ=2

Devuelve 1 para matrices de signos alternos, 0 de lo contrario. Pruébalo en línea! o verificar todos los casos de prueba .

Antecedentes

Sin tener en cuenta los ceros, cada fila y columna debe consistir en el patrón (1, -1) * 1 , es decir, ocurrencias alternas de 1 y -1 , comenzando y terminando con un 1 (por lo que la suma es 1 ).

Para verificar que este sea el caso, tomamos la matriz de todas las filas y columnas, y las unimos usando -1 como separador. Como todos los puntos finales son 1 , la matriz plana resultante satisface el patrón (1, -1) * 1 si y solo si las filas y columnas lo hacen.

Para la prueba real, calculamos la suma acumulativa de la matriz. Para una matriz de signos alterna, el resultado será una matriz de 0 y 1 que termina con un 1 .

Revertimos la suma acumulativa y la deduplicamos, manteniendo el orden de las ocurrencias iniciales de todos los elementos únicos. Para una entrada veraz, el resultado será la lista [1, 0] .

Para generar el booleano correspondiente, convertimos las sumas acumuladas duplicadas de binario a entero y probamos si el resultado es 2 .

Cómo funciona

;Zj-+\ṚQḄ=2  Main link. Argument: M (matrix / 2D array)

 Z           Zip; transpose M's rows and columns.
;            Concatenate M and zipped M.
  j-         Join, separating by -1.
    +\       Take the cumulative sum of the result.
      Ṛ      Reverse the array of partial sums.
       Q     Unique; deduplicate the partial sums.
        Ḅ    Unbinary; convert from base 2 to integer.
         =2  Test for equality with 2.

Dennis
fuente

2

MATL, 18 16 15 13 bytes

3 bytes guardados gracias a @Luis

t!h"@s1=@Xzdv

Esta solución acepta una matriz 2D como entrada y generará una matriz verdadera o falsey . Es importante tener en cuenta que en MATL, una matriz verdadera se compone de todos los elementos distintos de cero, mientras que un resultado falso tiene al menos un elemento cero. Aquí hay otra demostración de matrices de verdad / falsey .

Pruébalo en línea

Versión modificada para mostrar todos los casos de prueba

Explicación

        % Implicitly grab input matrix
t!      % Duplicate and transpose input
h       % Horizontally concatenate input with transpose. This allows us to 
        % process only columns since now the columns *also* contain the rows.
"       % For each column (of our column/row combined matrix)
  @s1=  % Compute the sum and ensure it is equal to 1
  @Xz   % Get the non-zeros
  d     % Compute the element-to-element difference. The 1 and -1 alternate only if
        % all these differences are non-zero
  v     % Vertically concatenate everything on the stack
        % Implicit end of loop and implicitly display truthy/falsey value

Suever
fuente

2

Julia, 36 bytes

!x=[x^0 x^0;-x -x'][:]|>cumsum⊆0:1

Pruébalo en línea!

Dennis
fuente

1

JavaScript (ES6), 112100 bytes

a=>!/(^|,)(?!0*10*(-10*10*)*(,|$))/.test(a.map(b=>b.join``)+','+a.map((_,i)=>a.map(b=>b[i]).join``))

Aplana la matriz y su transposición en cadenas, luego (ignorando 0s) verifica el patrón 1-11...1-11en cada cadena.

Editar: Guardado 12 bytes gracias a @PeterTaylor.

Neil
fuente

1

No es necesario para comprobar si el patrón -11-1...-11-1ya que desde las entradas alternativo y tienen suma positiva, tiene que ser uno más 1que -1, por lo que el patrón debe ser 1-11...1-11.

Peter Taylor

@PeterTaylor Ugh, esa es la segunda vez que he leído mal la pregunta. (Los comentarios relacionados con la primera vez se han eliminado desde entonces.)

Neil

El encabezado dice 110 bytes, pero solo son 100

Peter Taylor

1

@PeterTaylor Al menos los "12 bytes guardados gracias a @PeterTaylor" eran correctos.

Neil

1

Python 2, 63 60 bytes

s=0;x=input()
for r in x+zip(*x):
 for n in(-1,)+r:s+=[n][s]

La entrada es una lista de tuplas.

Esto termina con el código de salida 0 para alternar matrices de signos y el código de salida 1 de lo contrario. Esto es lo que hacen verdadero y falso , y, como se muestra en la sección de verificación, de hecho puede usarse como una condición en, por ejemplo, un script Bash.

Verificación

test-cases.txt

[(1,)]
[(1, 0), (0, 1)]
[(0, 1), (1, 0)]
[(0, 1, 0), (0, 0, 1), (1, 0, 0)]
[(0, 1, 0), (1, -1, 1), (0, 1, 0)]
[(0, 1, 0, 0), (0, 0, 1, 0), (1, 0, 0, 0), (0, 0, 0, 1)]
[(1, 0, 0, 0), (0, 0, 1, 0), (0, 1, -1, 1), (0, 0, 1, 0)]
[(0, 0, 1, 0), (0, 1, -1, 1), (1, -1, 1, 0), (0, 1, 0, 0)]
[(0, 0, 1, 0), (1, 0, -1, 1), (0, 1, 0, 0), (0, 0, 1, 0)]
[(0, 0, 1, 0, 0), (0, 1, -1, 1, 0), (1, -1, 1, 0, 0), (0, 1, 0, -1, 1), (0, 0, 0, 1, 0)]
[(0, 0, 1, 0, 0, 0, 0, 0), (1, 0, -1, 0, 1, 0, 0, 0), (0, 0, 0, 1, -1, 0, 0, 1), (0, 0, 1, -1, 1, 0, 0, 0), (0, 0, 0, 0, 0, 0, 1, 0), (0, 0, 0, 0, 0, 1, 0, 0), (0, 1, -1, 1, 0, 0, 0, 0), (0, 0, 1, 0, 0, 0, 0, 0)]
[(0, 0, 0, 0, 1, 0, 0, 0), (0, 0, 1, 0, -1, 1, 0, 0), (0, 0, 0, 1, 0, 0, 0, 0), (1, 0, 0, -1, 1, -1, 1, 0), (0, 1, -1, 1, -1, 1, 0, 0), (0, 0, 0, 0, 1, 0, 0, 0), (0, 0, 1, 0, 0, 0, 0, 0), (0, 0, 0, 0, 0, 0, 0, 1)]
[(0,)]
[(-1,)]
[(1, 0), (0, 0)]
[(0, 0), (0, 1)]
[(-1, 1), (1, 0)]
[(0, 1), (1, -1)]
[(0, 0, 0), (0, 0, 0), (0, 0, 0)]
[(0, 1, 0), (1, 0, 1), (0, 1, 0)]
[(-1, 1, 1), (1, -1, 1), (1, 1, -1)]
[(0, 0, 1), (1, 0, 0), (0, 1, -1)]
[(0, 1, 0, 0), (0, 0, 0, 1), (1, 0, 0, 0), (0, 0, 1, -1)]
[(0, 0, 1, 0), (0, 0, 1, 0), (1, 0, -1, 1), (0, 1, 0, 0)]
[(0, 0, 0, 1), (1, 0, 0, 0), (-1, 1, 1, 0), (1, 0, 0, 0)]
[(1, 0, 1, 0, -1), (0, 1, 0, 0, 0), (0, 0, 0, 0, 1), (0, 0, 0, 1, 0), (0, 0, 0, 0, 1)]
[(0, 0, 1, 0, 0), (0, 1, -1, 1, 0), (1, -1, 1, 0, 0), (0, 1, 1, -1, 0), (0, 0, -1, 1, 1)]
[(0, -1, 0, 1, 1), (1, -1, 1, -1, 1), (0, 1, 1, 0, -1), (1, 1, -1, 1, -1), (-1, 1, 0, 0, 1)]
[(0, 0, 1, 0, 0, 0, 0, 0), (1, 0, 1, 0, 1, 0, 0, 0), (0, 0, 0, 1, -1, 0, 0, 1), (0, 0, 1, -1, 1, 0, 0, 0), (0, 0, 0, 0, 0, 0, 1, 0), (0, 0, 0, 0, 0, 1, 0, 0), (0, 1, -1, 1, 0, 0, 0, 0), (0, 0, 1, 0, 0, 0, 0, 0)]

test-suite.sh

while read; do
        if python2 asmv.py <<< "$REPLY"; then
                echo "true"
        else
                echo "false"
        fi
done < test-cases.txt 2>&- | uniq -c

Salida

$ bash test-suite.sh
     12 true
     17 false

Cómo funciona

Sin tener en cuenta los ceros, cada fila y columna debe consistir en el patrón (1, -1) * 1 , es decir, ocurrencias alternas de 1 y -1 , comenzando y terminando con un 1 (por lo que la suma es 1 ).

Para verificar que este sea el caso, comprimimos / transponemos la matriz de entrada M , agregamos el resultado a M (que ahora consiste en una lista de filas y columnas) y anteponemos un -1 a cada fila / columna.

Por ejemplo, si M es una de las siguientes matrices (válida, inválida)

     0  1  0         0  0  0
     0  0  1         1  0  0
     1  0  0         0  1 -1

los resultados son

-1 | 0  1  0    -1 | 0  0  0
-1 | 0  0  1    -1 | 1  0  0
-1 | 1  0  0    -1 | 0  1 -1
------------    ------------
-1 | 0  0  1    -1 | 0  1  0
-1 | 1  0  0    -1 | 0  0  1
-1 | 0  1  0    -1 | 0  0 -1

La lectura de la matriz generada en fila debe dar como resultado una secuencia plana con patrón (-1, 1) * . Para verificar que este sea el caso, tomamos la suma acumulativa de todas las entradas, comenzando con la fila superior.

Para las matrices de ejemplo, esto da como resultado

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

Para una matriz de signos alternos válida, la salida consistirá en -1 'sy 0 ' s y, dado que cada -1 cancela el 1 anterior y viceversa, ningún otro número.

A primera vista, puede parecer que esto falla al verificar si la última columna termina con un 1 . Sin embargo, para una matriz n × n que contiene k ceros, las filas válidas contendrán n + k unos. Si todas las columnas, excepto la última, también fueran válidas, habría n + k - 1 en las columnas, lo cual es imposible.

Para comprobar que no hay otros números, almacenamos las sumas parciales en una variable s y las actualizamos para cada entrada de con matriz generada con s+=[n][s].

Si s = 0 o s = -1 , esto es equivalente a s+=n. Sin embargo, para todos los demás valores de s , causa un IndexError , por lo que Python termina inmediatamente con el código de salida 1 . Si esto no sucede en ningún momento, el programa termina limpiamente con el código de salida 0 .

Dennis
fuente

0

R, 54 bytes

Función anónima, utiliza la misma lógica que las respuestas de Dennis a Python 2, Jelly y Julia.

function(x)all(abs(cumsum(rbind(-1,cbind(t(x),x))))<2)

rturnbull
fuente

Verificación alterna de la matriz de signos

Casos de prueba

Respuestas:

Retina , 62 58 56 53 bytes

Explicación

Jalea, 15 bytes

Pyth, 16 bytes

Explicación:

Jalea , 11 bytes

Antecedentes

Cómo funciona

MATL, 18 16 15 13 bytes

Julia, 36 bytes

JavaScript (ES6), 112100 bytes

Python 2, 63 60 bytes

Verificación

Cómo funciona

R, 54 bytes