16

Uma matriz de sinal alternada é uma matriz nby que nconsiste nos números -1, 0, 1, de modo que:

A soma de cada linha e coluna é 1
As entradas diferentes de zero em cada linha e coluna se alternam no sinal

Essas matrizes generalizam matrizes de permutação e o número de matrizes para um dado nera de interesse por algum tempo. Eles ocorrem naturalmente durante o método de condensação de Dodgson para calcular determinantes da matriz (nomeado em homenagem a Charles Dodgson, mais conhecido como Lewis Carroll).

Aqui estão alguns exemplos de matrizes de sinais 4 por 4 alternadas:

 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

E aqui estão alguns exemplos de matrizes 4 por 4 que não são matrizes de sinais alternadas:

 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)

O seu programa ou função será dada uma npor nmatriz ( n >= 1) de -1S, 0s e 1s - saída de um valor truthy se a matriz dada é uma matriz sinal alternado, caso contrário, a saída de um valor Falsas.

Isso é código-golfe , então o objetivo é minimizar o número de bytes usados.

Casos de teste

Os seguintes casos de teste são fornecidos em um formato de lista 2D semelhante ao Python.

Verdade:

[[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
fonte

1

Relacionados

Peter Taylor

3

Retina , 62 58 56 53 bytes

A contagem de bytes assume a codificação ISO 8859-1 e \tdeve ser substituída por guias reais (0x09, que seriam transformadas em espaços pelo SE, caso contrário).

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

O formato de entrada é uma matriz em que cada coluna usa três caracteres alinhados à direita, por exemplo:

A saída é 0(falsy) ou 1(truthy).

Suíte de teste.(As primeiras linhas transformam o formato de entrada e permitem que o Retina execute vários casos de teste ao mesmo tempo.)

Explicação

Felizmente, a entrada é uma matriz quadrada: a transposição de quadrados é quase factível na Retina, enquanto a transposição de retângulos é uma dor enorme.

$
\t$`¶

Começamos anexando uma guia, toda a entrada novamente (usando o prefixo $`) e depois um avanço de linha no final (usando o apelido de Retina ¶). Estamos usando uma guia para separar as duas cópias, para podermos distinguir entre elas quando estivermos transpondo uma delas e, usando um caractere de espaço em branco, podemos salvar alguns bytes posteriormente.

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

Esta é a parte mais complicada: transpor a primeira cópia da matriz. A idéia é combinar as células na primeira cópia e depois classificá-las (de forma estável) pela posição horizontal. Combinamos as células com... (já que elas sempre têm três caracteres de largura) e medimos a posição horizontal com (.+)a parte de trás. Então, para garantir que apenas transponamos a primeira cópia, verificamos que podemos chegar ao início da string sem passar por uma guia.

Você pode perceber que isso também corresponderá a algumas cadeias de três bytes (que nem se alinham às células) na primeira linha da segunda cópia, porque o .+ elas podem passar pela guia. No entanto, isso não é um problema, porque a posição horizontal dessas correspondências é estritamente maior do que qualquer outra dentro da primeira cópia, portanto, essas correspondências permanecem em suas posições.

O resto é bastante simples:

T` 0

Removemos espaços e zeros da entrada.

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

E, finalmente, verificamos que toda a entrada consiste em linhas terminadas em espaço em branco 1(-11)*, ou seja, uma sequência alternada de 1e -1que começa e termina com 1(porque, caso contrário, não soma 1).

Martin Ender
fonte

3

Gelatina, 15 bytes

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

Experimente online!

;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.

Freira Furada
fonte

3

Pitão, 16 bytes

!sm-sM._+d_1U2+C

Experimente on-line: Demonstration or Test Suite

Explicação:

!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
fonte

3

Gelatina , 11 bytes

;Zj-+\ṚQḄ=2

Retorna 1 para matrizes de sinais alternadas, 0 caso contrário. Experimente online! ou verifique todos os casos de teste .

fundo

Desconsiderando os zeros, cada linha e coluna deve consistir no padrão (1, -1) * 1 , ou seja, ocorrências alternadas de 1 e -1 , iniciando e terminando com 1 (portanto, a soma é 1 ).

Para verificar se é esse o caso, pegamos a matriz de todas as linhas e colunas e as juntamos usando -1 como separador. Uma vez que todos os terminais são 1 's, os satisfaz matriz simples resultantes do padrão (1, -1) * 1 , se e somente se as linhas e colunas fazer.

Para o teste real, calculamos a soma cumulativa da matriz. Para uma matriz de sinais alternada, o resultado será uma matriz de 0 e 1 que termina com 1 .

Invertemos a soma cumulativa e a desduplicamos, mantendo a ordem das ocorrências iniciais de todos os elementos exclusivos. Para uma entrada confiável, o resultado será a lista [1, 0] .

Para gerar o booleano correspondente, convertemos as somas cumulativas duplicadas de binário em número inteiro e testamos se o resultado é 2 .

Como 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
fonte

2

MATL, 18 16 15 13 bytes

3 bytes salvos graças a @Luis

t!h"@s1=@Xzdv

Esta solução aceita uma matriz 2D como entrada e produzirá uma matriz de verdade ou falsey . É importante observar que em MATL, uma matriz de verdade é composta por todos os elementos diferentes de zero, enquanto um resultado de falsey possui pelo menos um elemento zero. Aqui está outra demonstração de matrizes truthy / falsey .

Experimente Online

Versão modificada para mostrar todos os casos de teste

Explicação

        % 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
fonte

2

Julia, 36 bytes

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

Experimente online!

Dennis
fonte

1

JavaScript (ES6), 112 100 bytes

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

Nivela a matriz e sua transposição em seqüências de caracteres, e (ignorando 0s) verifica o padrão 1-11...1-11em cada sequência.

Editar: salvou 12 bytes graças a @PeterTaylor.

Neil
fonte

1

Você não precisa para verificar o padrão -11-1...-11-1porque desde as entradas alternativo e têm soma positiva, deve haver um mais 1do que -1, por isso, o padrão deve ser 1-11...1-11.

Peter Taylor

@ PeterTaylor Ugh, é a segunda vez que interpreto mal a pergunta. (Os comentários relativos à primeira vez que já foram excluídos.)

Neil

O cabeçalho diz 110 bytes, mas é apenas 100

Peter Taylor

1

@PeterTaylor Pelo menos os "12 bytes salvos graças a @PeterTaylor" estavam corretos.

21416 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]

Entrada é uma lista de tuplas.

Isso termina com o código de saída 0 para matrizes de sinais alternadas e o código de saída 1, caso contrário. É isso que true e false fazem, e - como mostrado na seção de verificação - ele pode realmente ser usado como uma condição em, por exemplo, um script Bash.

Verificação

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

Resultado

$ bash test-suite.sh
     12 true
     17 false

Como funciona

Desconsiderando os zeros, cada linha e coluna deve consistir no padrão (1, -1) * 1 , ou seja, ocorrências alternadas de 1 e -1 , iniciando e terminando com 1 (portanto, a soma é 1 ).

Para verificar se é esse o caso, zipamos / transpusemos a matriz de entrada M , anexamos o resultado a M (agora composto por uma lista de linhas e colunas) e acrescentamos -1 a cada linha / coluna.

Por exemplo, se M é uma das seguintes matrizes (válida, inválida)

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

os resultados são

-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

A leitura da matriz gerada em linhas deve resultar em uma sequência plana com o padrão (-1, 1) * . Para verificar isso, pegamos a soma acumulada de todas as entradas, começando pela linha superior.

Para as matrizes de exemplo, isso resulta em

-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 uma matriz de sinais alternativos válida, a saída consistirá em -1 e 0 e - como cada -1 cancela o 1 anterior e vice-versa - nenhum outro número.

À primeira vista, isso pode parecer falha ao verificar se a última coluna termina com 1 . No entanto, para uma matriz n × n contendo k zeros, as linhas válidas conterão n + k linhas . Se todas as colunas, exceto a última, também fossem válidas, haveriam n + k - 1 nas colunas, o que é impossível.

Para testar se não há outros números, armazenamos as somas parciais em uma variável s e atualizamos para cada entrada de com matriz gerada com s+=[n][s].

Se s = 0 ou s = -1 , isso é equivalente a s+=n. No entanto, para todos os outros valores de s , causa um IndexError , portanto, o Python termina imediatamente com o código de saída 1 . Se isso não acontecer a qualquer momento, o programa será finalizado corretamente com o código de saída 0 .

Dennis
fonte

0

R, 54 bytes

Função anônima, usa a mesma lógica das respostas Python 2, Jelly e Julia de Dennis.

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

rturnbull
fonte

Verificação de matriz de sinal alternada

Casos de teste

Respostas:

Retina , 62 58 56 53 bytes

Explicação

Gelatina, 15 bytes

Pitão, 16 bytes

Explicação:

Gelatina , 11 bytes

fundo

Como funciona

MATL, 18 16 15 13 bytes

Julia, 36 bytes

JavaScript (ES6), 112 100 bytes

Python 2, 63 60 bytes

Verificação

Como funciona

R, 54 bytes