완전히 뒤집을 수있는 서브 매트릭스 6]

( 이 질문 에서 수학에 대해 영감을 얻음 )

정의

감안할 때 n x n정방 행렬 , 우리는 그것을 호출 할 수있는 몇 가지가 존재하는 경우 정방 행렬 B 가 등을 AB = BA = I NI n은 크기의 행렬 인 (주 대각선 행렬 들과 다른 것 ), 그리고 AB 그리고 BA 는 일반적인 행렬 곱셈을 나타냅니다 (나는 여기에 들어 가지 않을 것입니다-선형 대수 클래스를 가져 가십시오).invertiblen x nn x n10

그것에서, 우리는 호출 할 수있는 m x n행렬 C가 totally invertible 모든 경우 k x k의 서브 매트릭스 (아래 정의 됨) C가 모두 역함수이다 k > 1, k <= (smaller of m,n).

서브 매트릭스는 원래의 매트릭스로부터 다수의 행 및 / 또는 열을 삭제 한 후 결과 매트릭스로 정의된다. 예를 들어, 아래 3x3행렬 C 는 다음과 같이 첫 번째 행 과 가운데 열 을 제거하여 2x2하위 행렬 C ‘ 로 변환 할 수 있습니다 .1 2 32 5 8

C = [[1 2 3]
     [4 5 6]    -->  C' = [[4 6]
     [7 8 9]]              [7 9]]

서브 매트릭스 가능성은 여러 가지가 있으며, 위의 예는 단지 예일뿐입니다. 이 문제는 결과적인 하위 행렬이 k x k 정사각 행렬 인 경우에만 관심이 있습니다.

도전

입력 행렬이 주어지면 완전히 뒤집을 수 있는지 여부를 결정하십시오.

입력

  • 단일 크기의 행렬 m x n에서 임의의 적합한 형식 .
  • 일반성을 잃지 않으면 서 m <= n또는 m >= n코드 중 골퍼에 해당하는 것으로 가정 하여 입력 할 수 있습니다 (즉, 원하는 경우 조옮김 작업을 무료로 얻을 수 있음).
  • 입력 행렬 크기는 3 x 3언어보다 작을 수 없으며 언어가 처리 할 수있는 크기보다 크지 않습니다.
  • 입력 행렬은 Z + ( 양의 정수 ) 의 숫자 값으로 만 구성됩니다 .

출력

규칙

  • 전체 프로그램 또는 기능이 허용됩니다.
  • 표준 허점 은 금지되어 있습니다.
  • 이것은 이므로 모든 일반적인 골프 규칙이 적용되며 가장 짧은 코드 (바이트)가 이깁니다.

실시 예

Truthy

[[1 2 3]
 [2 3 1]
 [3 1 2]]

[[2 6 3]
 [1 12 2]
 [5 3 1]]

[[1 2 3 4]
 [2 3 4 1]
 [3 4 1 2]]

[[2  3  5  7  11]
 [13 17 19 23 29]
 [31 37 41 43 47]]


Falsey

[[1 2 3]
 [4 5 6]
 [7 8 9]]

[[1 6 2 55 3]
 [4 5 5 5  6]
 [9 3 7 10 4]
 [7 1 8 23 9]]

[[2 3 6]
 [1 2 12]
 [1 1 6]]

[[8 2 12 13 2]
 [12 7 13 12 13]
 [8 1 12 13 5]]



답변

젤리 , 26 24 23 20 19 17 16 바이트

@miles 덕분에 -1 바이트 (결정자를 취할 때 필요하지 않음 )
-2 바이트, @miles 다시! (불필요한 체인 분리 및 Ѐ빠른 사용 )

ZœcLÆḊ
œcЀJÇ€€Ȧ

TryItOnline! 또는 8 가지 테스트

어떻게?

œcЀJÇ€€Ȧ  - Main link: matrix as an array, M
    J      - range of length -> [1,2,...,len(a)] (n)
  Ѐ       - for each of right argument
œc         -     combinations of M numbering n
     Ç€€   - call the last link (1) as a monad for €ach for €ach
        Ȧ  - all truthy (any determinant of zero results in 0, otherwise 1)
                 (this includes an implicit flattening of the list)

ZœcLÆḊ - Link 1, determinants of sub-matrices: row selection, s
Z      - transpose s
   L   - length of s
 œc    - combinations of transposed s numbering length of s
    ÆḊ - determinant


답변

Mathematica 10.0, 34 바이트

#~Minors~n~Table~{n,Tr@#}~FreeQ~0&

6 물결표 체인 … 새로운 개인 기록!


답변

MATL, 57 바이트

tZyt:Y@!"@w2)t:Y@!"@w:"3$t@:)w@:)w3$)0&|H*XHx]J)]xxtZy]H&

물론 온라인으로 사용해 볼 수 있습니다!

입력은 ‘세로’방향이어야합니다 (nRows> = nColumns). 나는 이것이 가장 효율적인 해결책이 아닐 수도 있다고 생각한다. 그러나 적어도 나는 다른 사람들이 나를 능가 할 여지를 남겨두고있다. 나는이 특정 접근법을 더 짧게 만들 수있는 구체적인 힌트를 듣고 싶지만,이 엄청난 바이트 수는 다른 사람들이 완전히 다른 접근법으로 MATL 엔트리를 만들도록 영감을 줄 것이라고 생각합니다. 표시 0 경우 falsy, 또는 거대한 값 truthy이 (매트릭스 너무 큰 경우 신속하게 Inf를 될 것 1 추가 바이트를 위해, 하나는 대체 할 수있는 경우 H*H&Y) (논리적). @LuisMendo 덕분에 몇 바이트를 절약했습니다.

tZy  % Duplicate, get size. Note that n=<m.
%   STACK:  [m n], [C]
t: % Range 1:m
%   STACK:  [1...m], [m n], [C]
Y@   % Get all permutations of that range.
%   STACK:  [K],[m n],[C] with K all perms in m direction.
!"   % Do a for loop over each permutation.
%   STACK:  [m n],[C], current permutation in @.
@b   % Push current permutation. Bubble size to top.
%   STACK:  [m n],[pM],[C] with p current permutation in m direction.
2)t:Y@!" % Loop over all permutations again, now in n direction
%   STACK: [n],[pM],[C] with current permutation in @.
@w:" % Push current permutation. Loop over 1:n (to get size @ x @ matrices)
%   STACK: [pN],[pM],[C] with loop index in @.
3$t  % Duplicate the entire stack.
%   STACK: [pN],[pM],[C],[pN],[pM],[C]
@:)  % Get first @ items from pN
%   STACK: [pNsub],[pM],[C],[pN],[pM],[C]
w@:) % Get first @ items from pM
%   STACK: [pMsub],[pNsub],[C],[pN],[pM],[C]
w3$)  % Get submatrix. Needs a `w` to ensure correct order.
%   STACK: [Csub],[pN],[pM],[C]
0&|  % Determinant.
%   STACK: [det],[pN],[pM],[C]
H*XHx% Multiply with clipboard H.
%   STACK: [pN],[pM],[C]
]    % Quit size loop
%   STACK: [pN],[pM],[C]. Expected: [n],[pM],[C]
J)   % Get last element from pN, which is n.
%   STACK: [n],[pM],[C]
]    % Quit first loop
xxtZy% Reset stack to
%   STACK: [m n],[C]
]    % Quit final loop.
H& % Output H only.


답변