정의
감안할 때 n x n정방 행렬 , 우리는 그것을 호출 할 수있는 몇 가지가 존재하는 경우 정방 행렬 B 가 등을 AB = BA = I N 와 I 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 / falsey의 여부는 입력 매트릭스 용 완전 가역이다.
규칙
실시 예
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Ç€€Ȧ
어떻게?
œ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.