21

Dada uma matriz de números inteiros, teste se é o número um, o que significa que cada linha é um múltiplo do mesmo vetor. Por exemplo, em

 2   0  -20  10  
-3   0   30 -15
 0   0   0   0

cada linha é um múltiplo de 1 0 -10 5.

A mesma definição também funciona com colunas no lugar de linhas. Como alternativa, uma matriz é classificada como um, se for como uma tabela de multiplicação:

 *    1   0  -10  5
    ----------------
 2 |  2   0  -20  10  
-3 | -3   0   30 -15
 0 |  0   0   0   0

Atribuímos rótulos de linha r[i]e de coluna c[j]para que cada entrada da matriz M[i][j]seja o produto dos rótulos correspondentes como M[i][j] = r[i] * c[j].

Entrada:

Uma matriz inteira como um contêiner 2D de sua escolha. Por exemplo, uma lista de listas, uma matriz 2D ou similar. Você não deve usar a largura ou a altura como entradas adicionais, a menos que o formato da matriz exija.

A matriz pode ser não quadrada. Ele terá pelo menos uma entrada diferente de zero - você não precisa lidar com matrizes vazias ou zero.

Você pode supor que os números inteiros não causem problemas de estouro.

Saída:

Um valor consistente para matrizes de classificação um e um valor consistente diferente para outras matrizes.

Built-ins:

Você não pode usar nenhum componente interno para calcular a classificação ou verificar diretamente a classificação um. Você pode usar outros recursos internos, como autovalores, decomposições, etc., mas eu encorajo respostas positivas que não têm recursos internos, que fazem a maior parte do trabalho.

Casos de teste:

Primeiro lugar:

[[2, 0, -20, 10], [-3, 0, 30, -15], [0, 0, 0, 0]]
[[0, 0, 0], [0, 3, 0], [0, 0, 0]]
[[-10]]
[[0, 0, 0], [0, 4, 11], [0, -4, -11]]

Não no primeiro lugar:

[[-2, 1], [2, 4]]
[[0, 0, 3], [-22, 0, 0]]
[[1, 2, 3], [2, 4, 6], [3, 6, 10]]
[[0, -2, 0, 0], [0, 0, 0, 1], [0, 0, -2, 0]]

Entre os melhores:

Mostrar snippet de código

var QUESTION_ID=143528,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/143528/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Expandir snippet

code-golf decision-problem matrix linear-algebra xnor
fonte

2

Para os curiosos, uma resposta Mathematica usando builtins ficaria assim (16 bytes):MatrixRank@#==1&

JungHwan Min

2

Um belo teorema é que a classificação da coluna é igual à classificação da linha para matrizes dimensionais finitas.

Freira vazada

3

Precisamos nos preocupar com problemas de precisão de flutuação? Eles podem fazer uma matriz de rank-1 parecem posto 2, por exemplo

Luis Mendo

@LuisMendo Você precisa lidar com problemas de precisão, como valores próprios de 1.0000000001, mas pode assumir que a matriz não é grande e não foi escolhida especificamente para ser classificada incorretamente.

Xnor

13

Gelatina , 6 bytes

ẸÐfÆrE

Experimente online!

Como funciona

ẸÐfÆrE  Main link. Argument: M (2D array)

ẸÐf     Filter by any, removing rows of zeroes.
   Ær   Interpret each row as coefficients of a polynomial and solve it over the
        complex numbers.
     E  Test if all results are equal.

Precisão

Ærusa métodos numéricos; portanto, seus resultados geralmente são inexatos. Por exemplo, a entrada [6, -5, 1] , que representa o polinômio 6 - 5x + x² , resulta nas raízes 3.0000000000000004 e 1.9999999999999998 . No entanto, multiplicar todos os coeficientes de um polinômio pela mesma constante diferente de zero resulta em raízes igualmente inexatas. Por exemplo, Ærobtém as mesmas raízes para [6, -5, 1] e [6 × 10 ¹⁰⁰ , -5 × 10 ¹⁰⁰ , 10 ¹⁰⁰ ] .

Note-se que a precisão limitada dos tipos float e complexo pode levar a erros. Por exemplo, Ærobteria as mesmas raízes para [1, 1] e [10 ¹⁰⁰ , 10 ¹⁰⁰ + 1] . Como podemos assumir que a matriz não é grande e não foi escolhida especificamente para ser classificada incorretamente , isso deve ser bom.

Dennis
fonte

5

multiplicando todos os coeficientes de um polinômio pelos mesmos diferentes de zero constante resulta em raízes igualmente inexactas isso é uma abordagem brilhante

Luis Mendo

8

Haskell , 50 bytes

rpega uma lista de listas de se Integerretorna Falsese a matriz tiver uma classificação, Truecaso contrário.

r l=or[map(x*)b<map(y*)a|a<-l,b<-l,(x,y)<-zip a b]

Experimente online!

Como funciona

Gera todos os pares de linhas ae b(incluindo linhas iguais) e, para cada par, permite xe ypercorre os elementos correspondentes.
Multiplica a linha bpor xe a linha apor y. A matriz terá uma classificação se e somente se os resultados forem sempre iguais.
Como os pares são gerados em ambas as ordens, <pode ser usado para verificar se há alguma desigualdade. A lista de resultados do teste é combinada com or, indicando Truese existem linhas não proporcionais.

Ørjan Johansen
fonte

7

Mathematica, 51 33 bytes

RowReduce@#~Count~Except@{0..}<2&

Entrada

[{{2,0, -20,10}, {- 3,0,30, -15}, {0,0,0,0}}]

-14 bytes do usuário202729 Mais
3 bytes salvos de junghwanmin

J42161217
fonte

Sugiro que, em vez de construir uma tabela com comprimento igual ao de First@#, você pode calcular, 0First@#pois 0 multiplica com tudo é 0 e a multiplicação é listável. Além disso, você pode considerar o uso Tr[1^<list>]para calcular o comprimento de uma lista.

user202729

muito legal.Eu vou editar!

J42161217

Em vez de 0#&@@#, {0..}também funcionaria. E então Infixfunciona, para que o código final possa ser RowReduce@#~Count~{0..}==Tr[1^#]-1&, economizando 2 bytes.

JungHwan Min 23/09/17

Na verdade, Exceptpode ser usado para se livrar de Trcoisas. -3 bytes:RowReduce@#~Count~Except@{0..}==1&

JungHwan Min 23/09

Eu acho que a matriz reduzida de linha é garantida como diferente de zero (porque a matriz original é diferente de zero), portanto, o resultado da contagem será um número inteiro positivo e, portanto, <2pode ser usado em vez de ==1.

User202729

4

JavaScript (ES6), 68 67 65 bytes

Este é baseado na resposta 05AB1E de Neil e é significativamente mais eficiente do que minha abordagem original.

Retorna falsepara a classificação um e truecaso contrário.

f=(a,R,V,X)=>a.some(r=>r.some((v,x)=>R?v*V-r[X]*R[x]:f(a,r,v,x)))

Casos de teste

Mostrar snippet de código

f=(a,R,V,X)=>a.some(r=>r.some((v,x)=>R?v*V-r[X]*R[x]:f(a,r,v,x)))

console.log(f([[2, 0, -20, 10], [-3, 0, 30, -15], [0, 0, 0, 0]]))
console.log(f([[0, 0, 0], [0, 3, 0], [0, 0, 0]]))
console.log(f([[-10]]))
console.log(f([[0, 0, 0], [0, 4, 11], [0, -4, -11]]))

console.log(f([[-2, 1], [2, 4]]))
console.log(f([[0, 0, 3], [-22, 0, 0]]))
console.log(f([[1, 2, 3], [2, 4, 6], [3, 6, 10]]))
console.log(f([[0, -2, 0, 0], [0, 0, 0, 1], [0, 0, -2, 0]]))

Expandir snippet

Resposta original, 84 bytes

Retorna falsepara a classificação um e truecaso contrário.

a=>a.some(r=>r.some((x,i)=>(isNaN(x/=a.find(r=>r.some(x=>x))[i])?r:1/r[0]?r=x:x)-r))

Casos de teste

Mostrar snippet de código

let f =

a=>a.some(r=>r.some((x,i)=>(isNaN(x/=a.find(r=>r.some(x=>x))[i])?r:1/r[0]?r=x:x)-r))

console.log(f([[2, 0, -20, 10], [-3, 0, 30, -15], [0, 0, 0, 0]]))
console.log(f([[0, 0, 0], [0, 3, 0], [0, 0, 0]]))
console.log(f([[-10]]))
console.log(f([[0, 0, 0], [0, 4, 11], [0, -4, -11]]))

console.log(f([[-2, 1], [2, 4]]))
console.log(f([[0, 0, 3], [-22, 0, 0]]))
console.log(f([[1, 2, 3], [2, 4, 6], [3, 6, 10]]))
console.log(f([[0, -2, 0, 0], [0, 0, 0, 1], [0, 0, -2, 0]]))

Expandir snippet

Quão?

a => a.some(r =>          // given a matrix a, for each row r of a:
  r.some((x, i) =>        //   for each value x of r at position i:
    (                     //
      isNaN(x /=          //     divide x by a[ref][i]
        a.find(r =>       //       where ref is the index of the first row that
          r.some(x => x)  //       contains at least one non-zero value
        )[i]              //       (guaranteed to exist by challenge rules)
      ) ?                 //     we get NaN for 0/0, in which case:
        r                 //       use r, so that this column is ignored
      :                   //     else:
        1 / r[0] ?        //       if r is still holding the current row:
          r = x           //         set it to x (either a float, +Inf or -Inf)
        :                 //       else:
          x               //         use x
    ) - r                 //     subtract r from the value set above (see table)
  )                       //   end of some()
)                         // end of every()

A subtração que é executada no final do código pode levar a muitas situações diferentes, resumidas abaixo:

A                   | B              | A - B       | False / True
--------------------+----------------+-------------+-------------
array of 1 number   | same array     | 0           | False
array of 2+ numbers | same array     | NaN         | False
a number            | same number    | 0           | False
+Infinity           | +Infinity      | NaN         | False
-Infinity           | -Infinity      | NaN         | False
a number            | another number | <> 0        | True
+Infinity           | -Infinity      | +Infinity   | True
-Infinity           | +Infinity      | -Infinity   | True
a number            | +/-Infinity    | +/-Infinity | True
+/-Infinity         | a number       | +/-Infinity | True

O teste falha, assim que receber um valor truthy: isto acontece quando nos deparamos com duas proporções diferentes (excepto 0/0 ) entre a (i, y) e um (i, r) em qualquer linha y da matriz, onde r é o índice de uma linha diferente de zero.

Arnauld
fonte

Huh, eu só estava me perguntando isso ...

Neil

@ Neil Deseja publicá-lo como uma nova resposta? Apenas me avise.

Arnauld 23/09

3

Python 2 + numpy, 58 bytes

lambda m:sum(linalg.svd(m)[1]>1e-10)==1
from numpy import*

Experimente online!

Crédito para isso .

totalmente humano
fonte

Alguém poderia usar em 1e-9vez de 1e-10?

Jonathan Frech

3

Gelatina , 12 bytes

ẸÐfµ÷"Ð€ZE€Ẹ

Experimente online!

Explicação

ẸÐfµ÷"Ð€ZE€Ẹ  Main link
 Ðf           Filter; keep all elements where
Ẹ             At least one element is truthy (remove zero-rows)
      Ð€      For each row on the right side
    ÷"        Divide it by each row in the original
        Z     Zip the array
          €   For each submatrix
         E    Are all rows equal?
           Ẹ  Is at least one of the elements from above truthy?

A explicação pode estar um pouco incorreta, pois esta é minha interpretação do golfe em milhas do meu algoritmo original

-5 bytes graças a milhas

HyperNeutrino
fonte

... Seu código é viciado em dinheiro. (Estou recebendo deja vu ...)

totallyhuman

@icrieverytim Ei, pelo menos o número de cifrões é menos da metade do comprimento do código dessa vez! : P

HyperNeutrino

1

@icrieverytim corrigiu um erro e agora ainda menos cifrões: P

HyperNeutrino 23/09/17

Eu acredito que este deve funcionar também para 12 bytes ẸÐfµ÷"Ð€ZE€Ẹ TIO

milhas

@miles Oh legal! A abordagem para o seu caso é um pouco diferente (eu acho?) Para que você possa postar isso como sua própria resposta de que você gostaria :)

HyperNeutrino

3

05AB1E , 16 bytes

2ãεø2ãε`R*`Q}W}W

Experimente online! Usa a propriedade da tabela de multiplicação que os cantos opostos de qualquer retângulo têm o mesmo produto. Explicação:

2ãε           }     Loop over each pair of rows
   ø                Transpose the pair into a row of pairs
    2ãε     }       Loop over each pair of columns
       `R*`Q        Cross-multiply and check for equality
             W W    All results must be true

Neil
fonte

3

TI-Basic (série TI-83), 28 27 28 bytes (62 caracteres)

:Prompt [A]
:{0→X
:Matr►list(ref([A])ᵀ,L₁,X
:not(max(abs(ᶫX

Calcula a forma de escalão de linha da matriz [A], armazena sua primeira linha (a ser descartada) L₁e a segunda linha em ᶫX. Então max(abs(ᶫXserá zero se ᶫXconsistir apenas de zeros, e um valor positivo caso contrário, que not(mudará para 1 se a matriz for classificada como um, 0 caso contrário.

Para uma matriz de 1 linha, ᶫXé definido como {0}e não é alterado quando tentamos examinar a segunda linha inexistente da matriz.

-1 byte graças a Scott Milner

+1 byte para corrigir erro de dimensão para matrizes de 1 linha. Acontece que o Matr►list( comando reclama se você tentar extrair a segunda linha de uma matriz com apenas uma linha; no entanto, se você tentar extrair a primeira e a segunda linha da matriz, ela falhará silenciosamente.

Misha Lavrov
fonte

1

Você pode salvar um byte em Prompt [A]vez de Ans→[A].

Scott Milner

@ScottMilner Thanks! Provavelmente existe uma maneira de evitar isso, se usarmos algo como ClrListinicializar ᶫX, mas ainda não consegui que isso funcionasse em menos espaço.

Misha Lavrov #

Livre-se da segunda linha, pois Matr►list(ela substituirá a lista, mesmo que ela não exista, e você economizará 5 bytes.

kamoroso94

1

@ kamoroso94 O ponto da segunda linha não é criar uma lista quando ela não existe: o ponto da segunda linha é criar um valor padrão para a segunda linha quando a matriz tiver apenas uma linha. Se você se livrar da segunda linha, o código trava para matrizes 1xN.

Misha Lavrov #

2

@ kamoroso94 Teríamos que substituir L1 por ᶫY, não Y; caso contrário, a calculadora pensará "extrair a Y-ésima linha da matriz para ᶫX", não "extrair a primeira linha para ᶫY e a segunda linha para ᶫX".

Misha Lavrov

3

Braquilog , 27 bytes

{⊇Ċ}ᶠzᵐ{↰₁ᶠ{⟨hz{t↔}⟩×ᵐ=}ᵐ}ᵐ

Experimente online!

Usa a abordagem de Neil de "produtos de cantos opostos de cada retângulo devem ser iguais". O produto cruzado é caro e leva 10 bytes inteiros, mas ainda é mais curto do que qualquer abordagem baseada em divisão que tentei, principalmente por causa da estipulação de duas saídas consistentes para verdade e falsey na pergunta - fazer da falsey ser apenas um false., e às vezes não um erro de divisão por zero, usa muitos bytes.

{⊇Ċ}ᶠzᵐ{↰₁ᶠ{⟨hz{t↔}⟩×ᵐ=}ᵐ}ᵐ
{⊇Ċ}ᶠ                        Get each pair of rows from the matrix
                             eg.: [ [[a, b, c], [k, l, m]], ... ]
     zᵐ                      Zip each pair's elements
                                  [ [[a, k], [b, l], [c, m]], ... ]
       {                 }ᵐ  Map this over each pair of rows:
                                  [[a, k], [b, l], [c, m]]
        ↰₁ᶠ                  Get each pair of paired elements from the rows
                                  [[[a, k], [b, l]], [[b, l], [c, m]], [[a, k], [c, m]]]
           {           }ᵐ    Map this over each pair of pairs
                                  [[a, k], [b, l]]
            ⟨hz{t↔}⟩         Zip the first pair with the reverse of the second
                                  [[a, l], [k, b]]
                    ×ᵐ       Multiply within each sublist
                                  [al, kb]
                      =      The results should be equal
                             (If the results are unequal for any pair, the whole predicate fails,
                              and outputs false.)

Abordagem alternativa com base na divisão por elementos ( 30 bytes ):

{≡ᵉ¬0&}ˢ\↰₁ˢ{c×¬0&⟨hz∋⟩ᶠ/ᵐ²=ᵐ}

Experimente online!

sundar - Restabelecer Monica
fonte

2

Geléia , 9 bytes

ẸÐf÷g/$€E

Experimente online!

ẸÐf         Discard zero rows
   ÷  $€    Divide each row by
    g/        its greatest common divisor
        E   Does this list have only one unique element?

Lynn
fonte

1

SageMath, 40 bytes

lambda M:any(M.rref()[1:])*(M.nrows()>1)

Experimente online

Essa função anônima retornará Falsese a matriz estiver na primeira posição e Truecaso contrário.

A função pega uma matriz Mcomo entrada, converte-a na forma de escalão de linha reduzida ( M.rref()) e testa se anyas linhas após a primeira são diferentes de zero. Então, esse valor é multiplicado por M.nrows()>1(a matriz possui mais de uma linha?).

Mego
fonte

1

Python 3 , 93 91 bytes

lambda m,e=enumerate:any(h*g-r[j]*s[i]for r in m for i,h in e(r)for s in m for j,g in e(s))

Experimente online!

Como funciona

Verifica se algum menor de 2 tem determinante diferente de zero. Se for esse o caso, a classificação deve ser pelo menos 2: "Um menor menor que não desaparece (submatriz p × p com determinante diferente de zero) mostra que as linhas e colunas dessa submatriz são linearmente independentes e, portanto, essas linhas e as colunas da matriz completa são linearmente independentes (na matriz completa), portanto, a classificação de linha e coluna é pelo menos tão grande quanto a classificação determinante "(da Wikipedia )

Nota: raspou dois bytes graças ao comentário do usuário71546.

Luca Citi
fonte

1

91 - menor se colocar enumerate para os argumentos da função e eliminando assim a necessidade de f=:lambda m,e=enumerate:any(h*g-r[j]*s[i]for r in m for i,h in e(r)for s in m for j,g in e(s))

Shieru Asakoto

@ user71546 Obrigado! Feito!

Luca Citi

0

Pari / GP , 18 bytes

a->#matimage(a)==1

matimage fornece uma base da imagem da transformação linear definida pela matriz.

Experimente online!

alefalpha
fonte

A matriz é de classificação um?

Respostas:

Gelatina , 6 bytes

Como funciona

Precisão

Haskell , 50 bytes

Como funciona

Mathematica, 51 33 bytes

JavaScript (ES6), 68 67 65 bytes

Casos de teste

Resposta original, 84 bytes

Casos de teste

Quão?

Python 2 + numpy, 58 bytes

Gelatina , 12 bytes

Explicação

05AB1E , 16 bytes

TI-Basic (série TI-83), 28 27 28 bytes (62 caracteres)

Braquilog , 27 bytes

Geléia , 9 bytes

SageMath, 40 bytes

Python 3 , 93 91 bytes

Pari / GP , 18 bytes