001 | public class Matrix { |
002 | public static final int NOT_FOUNT = -2147483646; |
003 | private double[][] matrix; |
004 | private int row, col; |
005 |
006 | /** |
007 | * 0행렬 만들기 |
008 | * |
009 | * @param row |
010 | * 행 크기 |
011 | * @param col |
012 | * 열 크기 |
013 | * @return |
014 | */ |
015 | public static Matrix zeros(int row, int col) { |
016 | Matrix temp = new Matrix(row, col); |
017 | temp.setZeroMatrix(); |
018 | return temp; |
019 | } |
020 |
021 | /** |
022 | * i * i 크기의 0행렬 |
023 | * |
024 | * @param i |
025 | * @return |
026 | */ |
027 | public static Matrix zeros(int i) { |
028 | return Matrix.zeros(i, i); |
029 | } |
030 |
031 | /** |
032 | * 1행렬 만들기 |
033 | * |
034 | * @param row |
035 | * 행 크기 |
036 | * @param col |
037 | * 열 크기 |
038 | * @return |
039 | */ |
040 | public static Matrix ones(int row, int col) { |
041 | Matrix temp = new Matrix(row, col); |
042 | temp.setOnesMatrix(); |
043 | return temp; |
044 | } |
045 |
046 | /** |
047 | * i * i 크기의 1행렬 |
048 | * |
049 | * @param i |
050 | * @return |
051 | */ |
052 | public static Matrix ones(int i) { |
053 | return Matrix.ones(i, i); |
054 | } |
055 |
056 | /** |
057 | * i*i의 단위행렬 |
058 | * |
059 | * @param i |
060 | * @return |
061 | */ |
062 | public static Matrix unitMatrix(int i) { |
063 | Matrix temp = new Matrix(i); |
064 | temp.setUnitMatrix(); |
065 | return temp; |
066 | } |
067 |
068 | /** |
069 | * 행렬식을 계산한다. |
070 | * determinant()을 사용할것 |
071 | * |
072 | * @param target |
073 | * @return target의 행렬식 |
074 | */ |
075 | @Deprecated |
076 | public static double determinant1(Matrix target) { |
077 | // 라이프니츠 공식에 의한 행렬식 계산 |
078 | double det = 0; |
079 | if (target.getRowSize() == target.getColSize()) { |
080 | double[][] A = target.getMatrix(); |
081 | if (A.length == 1) { |
082 | return A[0][0]; |
083 | } else { |
084 | for (int i = 0; i < A[0].length; i++) { |
085 | det += A[0][i] * target.cofactor(0, i);// 재귀 |
086 | // 호출 |
087 | } |
088 | } |
089 | return det; |
090 | } else { |
091 | System.out.println("행렬식을 구할수 없습니다."); |
092 | return NOT_FOUNT; |
093 | } |
094 |
095 | } |
096 |
097 | /** |
098 | * 가우스 소거법에 의한 행렬식 계산 |
099 | * |
100 | * @param target |
101 | * @return |
102 | */ |
103 | public static double determinant(Matrix target) { |
104 | if (target.getRowSize() == target.getColSize()) { |
105 | double[][] temp = new double[target.row][target.row]; |
106 | // temp=getMatrix()로 하면 레퍼런스로 되어서 본래 행렬이 |
107 | // 변경됨 |
108 | for (int i = 0; i < target.row; i++) { |
109 | for (int j = 0; j < target.row; j++) { |
110 | temp[i][j] = target.matrix[i][j]; |
111 | } |
112 | } |
113 | for (int n = 0; n < temp.length; n++) { |
114 | if (temp[n][n] == 0) { |
115 | for (int a = n; a < temp.length; a++) { |
116 | if (temp[a][n] != 0) { |
117 | for (int b = n; b < temp.length; b++) { |
118 | temp[n][b] += temp[a][b]; |
119 | } |
120 | break; |
121 | } |
122 | } |
123 | if (temp[n][n] == 0) { |
124 | System.out.println(n + "ss"); |
125 | return 0; |
126 | } |
127 | } |
128 | for (int i = n + 1; i < temp.length; i++) { |
129 | { |
130 | for (int j = temp[0].length - 1; j >= n; j--) { |
131 | temp[i][j] = temp[i][j] - temp[i][n] * temp[n][j] |
132 | / temp[n][n];// 수정필요 |
133 | } |
134 | } |
135 | } |
136 | // new Matrix(temp).displayMatix(); |
137 | // //test |
138 | // System.out.println("aaa"); |
139 | } |
140 | double sum = 1; |
141 | for (int i = 0; i < temp.length; i++) { |
142 | sum *= temp[i][i]; |
143 | } |
144 | // new Matrix(temp).displayMatix(); |
145 | return sum; |
146 | } else { |
147 | System.out.println("행렬식을 구할수 없습니다."); |
148 | return NOT_FOUNT; |
149 | } |
150 | } |
151 |
152 | /** |
153 | * 여행렬 구하기 |
154 | * |
155 | * @param target |
156 | * @param row |
157 | * @param col |
158 | * @return target의 row 행과 col 열을 제외한 여행렬 |
159 | */ |
160 | public static double cofactor(Matrix target, int row, int col) { |
161 | Matrix temp = target.minor(row, col); |
162 |
163 | return temp.determinant() * Math.pow((-1), (row + col)); |
164 | } |
165 |
166 | /** |
167 | * 소행렬 구하기 |
168 | * |
169 | * @param target |
170 | * @param removeRow |
171 | * @param removeCol |
172 | * @return target의 row 행과 col 열을 제외한 소행렬 |
173 | */ |
174 | public Matrix minor(int removeRow, int removeCol) { |
175 | int ar = 0, ac = 0; |
176 | double temp[][] = new double[row - 1][col - 1]; |
177 |
178 | for (int r = 0; r < row; r++) { |
179 | for (int c = 0; c < col; c++) { |
180 | if (!(r == removeRow || c == removeCol)) { |
181 | temp[ar][ac] = matrix[r][c]; |
182 | if (++ac >= col - 1) { |
183 | if (++ar < row - 1) |
184 | ac = 0; |
185 | } |
186 | } |
187 | } |
188 | } |
189 | return new Matrix(temp); |
190 | } |
191 |
192 | /** |
193 | * 행렬의 합 |
194 | * |
195 | * @param A |
196 | * @param B |
197 | * @return |
198 | */ |
199 | public static Matrix plus(Matrix A, Matrix B) { |
200 | double[][] temp = Matrix.zeros(A.row, A.col).getMatrix(); |
201 | double[][] tempA = A.getMatrix(); |
202 | double[][] tempB = B.getMatrix(); |
203 | if (equalSize(A, B)) { |
204 | for (int i = 0; i < tempA.length; i++) { |
205 | for (int k = 0; k < tempA[0].length; k++) { |
206 | temp[i][k] = tempA[i][k] + tempB[i][k]; |
207 | } |
208 | } |
209 | return new Matrix(temp); |
210 | } |
211 | return new Matrix(temp); |
212 | } |
213 |
214 | /** |
215 | * 행렬의 차 |
216 | * |
217 | * @param A |
218 | * @param B |
219 | * @return |
220 | */ |
221 | public static Matrix minus(Matrix A, Matrix B) { |
222 | double[][] temp = Matrix.zeros(A.row, A.col).getMatrix(); |
223 | double[][] tempA = A.getMatrix(); |
224 | double[][] tempB = B.getMatrix(); |
225 | if (equalSize(A, B)) { |
226 | for (int i = 0; i < tempA.length; i++) { |
227 | for (int k = 0; k < tempA[0].length; k++) { |
228 | temp[i][k] = tempA[i][k] - tempB[i][k]; |
229 | } |
230 | } |
231 | return new Matrix(temp); |
232 | } |
233 | return new Matrix(temp); |
234 | } |
235 |
236 | /** |
237 | * 행렬의 모양 비교 |
238 | * |
239 | * @param A |
240 | * @param B |
241 | * @return |
242 | */ |
243 | public static boolean equalSize(Matrix A, Matrix B) { |
244 | if (A.getRowSize() == B.getRowSize() |
245 | && A.getColSize() == B.getColSize()) { |
246 | return true; |
247 | } else { |
248 | return false; |
249 | } |
250 | } |
251 |
252 | Matrix(int i) // 행,열 의 크기가 같은 생성자 |
253 | { |
254 | this.row = i; |
255 | this.col = i; |
256 | matrix = new double[i][i]; |
257 | for (int a = 0; a < i; a++) { |
258 | for (int b = 0; b < i; b++) { |
259 | matrix[a][b] = (int) (Math.random() * 10 * Math.pow(-1, |
260 | (int) Math.random() * 10)); |
261 | } |
262 | } |
263 | } |
264 |
265 | Matrix(int row, int col) // 행 열의 크기가 다른 생성자 |
266 | { |
267 | this.row = row; |
268 | this.col = col; |
269 | matrix = new double[row][col]; |
270 | for (int i = 0; i < row; i++) { |
271 | for (int k = 0; k < col; k++) { |
272 | matrix[i][k] = (int) (Math.random() * 10 * Math.pow(-1, |
273 | (int) Math.random() * 10)); |
274 | } |
275 | } |
276 | } |
277 |
278 | public Matrix(double[][] temp) // 임의의 행렬을 입력받는 생성 |
279 | { |
280 | this.matrix = temp; |
281 | row = temp.length; |
282 | col = temp[0].length; |
283 | } |
284 |
285 | /** |
286 | * |
287 | * @return 행렬 원소중 Not a Number 인 원소가 있다면 true |
288 | */ |
289 | public boolean isNaN() { |
290 | for (int i = 0; i < col; i++) |
291 | for (int j = 0; j < row; j++) |
292 | if (Double.isNaN(matrix[j][i])) |
293 | return false; |
294 | return true; |
295 | } |
296 |
297 | /** |
298 | * 자기 자신을 영행렬로 바꾸기 |
299 | */ |
300 | public void setZeroMatrix() { |
301 | for (int i = 0; i < row; i++) { |
302 | for (int k = 0; k < col; k++) { |
303 | matrix[i][k] = 0; |
304 | } |
305 | } |
306 | } |
307 |
308 | /** |
309 | * 자기 자신을 모두 1인 행렬로 바꿈 |
310 | */ |
311 | public void setOnesMatrix() { |
312 | for (int i = 0; i < row; i++) { |
313 | for (int k = 0; k < col; k++) { |
314 | matrix[i][k] = 1; |
315 | } |
316 | } |
317 | } |
318 |
319 | /** |
320 | * 자기자신을 단위행렬로 |
321 | */ |
322 | public void setUnitMatrix() { |
323 | setZeroMatrix(); |
324 | for (int i = 0; i < row; i++) { |
325 | matrix[i][i] = 1; |
326 | } |
327 | } |
328 |
329 | public void displayMatix() { |
330 | System.out.println(this); |
331 | } |
332 |
333 | @Override |
334 | public String toString() { |
335 | String temp = ""; |
336 | for (int i = 0; i < row; i++) { |
337 | for (int k = 0; k < col; k++) { |
338 | if (matrix[i][k] == -0) { |
339 | // 이 부분이 없으면 -0과 0이 동시에 나오게 된다 |
340 | matrix[i][k] = 0; |
341 | } |
342 | temp += Double.toString(matrix[i][k]); |
343 | // C 의 printf와 유사 |
344 | if (k != col - 1) { |
345 | temp += ", "; |
346 | } |
347 | } |
348 | temp += System.getProperty("line.separator"); |
349 | } |
350 | return temp; |
351 | } |
352 |
353 | /** |
354 | * 여인수 |
355 | * |
356 | * @param row |
357 | * @param col |
358 | * @return |
359 | */ |
360 | public double cofactor(int row, int col) { |
361 | return minor(row, col).determinant() * Math.pow((-1), row + col); |
362 | } |
363 |
364 | /** |
365 | * @param temp |
366 | * 행렬의 값을 temp로 바꿈 |
367 | */ |
368 | public void setMatrix(double temp[][]) { |
369 | // 행렬 내용 수정 temp와 matrix가 다를시 문제가 생길수 있음 |
370 | // length로 행과 열의 길이 파악 |
371 | this.row = temp.length; |
372 | this.col = temp[0].length; |
373 | this.matrix = temp; |
374 | } |
375 |
376 | /** |
377 | * 전치행렬 |
378 | * |
379 | * @return 이 행렬의 전치행렬 |
380 | */ |
381 | public Matrix transpose() { |
382 | Matrix tempM = new Matrix(col, row); |
383 | double temp[][] = new double[col][row]; |
384 | for (int i = 0; i < row; i++) { |
385 | for (int k = 0; k < col; k++) { |
386 | temp[k][i] = matrix[i][k]; |
387 | } |
388 | } |
389 | tempM.setMatrix(temp); |
390 | return tempM; |
391 | } |
392 |
393 | /** |
394 | * 행렬의 상수배 |
395 | * |
396 | * @param m |
397 | * 행렬에 곱할 수 |
398 | * @return 현재 행렬의 m 배된 행렬 |
399 | */ |
400 | public Matrix multiply(double m) { |
401 | Matrix temp = new Matrix(row, col); |
402 | for (int i = 0; i < row; i++) { |
403 | for (int k = 0; k < col; k++) { |
404 | temp.matrix[i][k] = this.matrix[i][k] * m; |
405 | } |
406 | } |
407 | return temp; |
408 | } |
409 |
410 | /** |
411 | * 행렬의 곱 |
412 | * |
413 | * @param secMatrix |
414 | * 현재 행렬에 곱해질 행렬 |
415 | * @return 현재 행렬X secMatrix |
416 | */ |
417 | public Matrix multiply(Matrix secMatrix) // 행렬*행렬 |
418 | { |
419 | // Matrix temp; |
420 | double[][] temp; |
421 | // 곱하기 위해 앞쪽 행렬의 열과 뒷쪽행렬의 행이 같아야함 |
422 | if (this.col == secMatrix.row) { |
423 | temp = Matrix.zeros(this.row, secMatrix.col).getMatrix(); |
424 | double[][] A = this.getMatrix(); |
425 | double[][] B = secMatrix.getMatrix(); |
426 | for (int i = 0; i < this.row; i++) { |
427 | for (int j = 0; j < secMatrix.col; j++) { |
428 | for (int a = 0; a < this.col; a++) { |
429 | // System.out.println("i="+i+" k="+k+" a="+a); |
430 | // //테스트 |
431 | temp[i][j] += A[i][a] * B[a][j]; |
432 | } |
433 | } |
434 | } |
435 | return new Matrix(temp); |
436 | } else { |
437 | System.out.println("계산할 수 없습니다."); |
438 | return Matrix.zeros(1); |
439 | } |
440 |
441 | } |
442 |
443 | /** |
444 | * 역행렬 |
445 | * invers()를 사용할것 |
446 | * |
447 | * @return 현재 행렬의 역행렬 |
448 | */ |
449 | @Deprecated |
450 | public Matrix invers1() { |
451 | // 역행렬// 행렬의 크기가 8x8이 넘어가면 출력하는데 시간이 너무 오래걸린다. |
452 | // 알고리즘의 최적화가 필요한듯 하다. ->invers() 알고리즘 변경 |
453 | Matrix temp = null; |
454 | if (row == col) // 행==열인 행렬인지 확인 |
455 | { |
456 | temp = Matrix.zeros(row); |
457 | for (int i = 0; i < row; i++) { |
458 | for (int j = 0; j < row; j++) { |
459 | temp.matrix[i][j] = cofactor(i, j); |
460 | // i행j열의 값 =여인수(i,j) |
461 | } |
462 |
463 | } |
464 | temp = temp.transpose();// 전치 |
465 | double det = determinant1(this); |
466 | // 원래 행렬의 행렬식계산 |
467 | if (det != 0) { |
468 | return temp.multiply(1.0 / det); |
469 | // 마지막으로 행렬식으로 나눠준다. |
470 | } else { |
471 | System.out.println("역행렬이 없습니다."); |
472 | // 행렬식==0이면 역행렬이 없다. |
473 | return Matrix.zeros(1); |
474 | } |
475 |
476 | } else { |
477 | System.out.println("행과 열의 크기가 같지 않습니다."); |
478 | return Matrix.zeros(1); |
479 | } |
480 | } |
481 |
482 | /** |
483 | * 역행렬<br> |
484 |
485 |
486 |
487 | * 가우스 조던 소거법 |
488 | * invers1에 비하여 매우 빠르다 invers 는 9차 이상의 행렬에서 |
489 | * 동작속도를 보장할수 없다. |
490 | * 하지만 이것은 100차 행렬이 넘어가도 빠른속도로 계산이 가능하다. |
491 | * 하지만 역행렬이 존재 하지 않는 행렬에서도 답이 나오므로 선행해서 걸러낼 필요가 |
492 | * 있다. |
493 | * 마지막에 원래 행렬과 만들어진 역행렬을 곱해서 단위행렬이 나오는지 검사 |
494 | * |
495 | * @return 현재 행렬의 역행렬. 역행렬을 만들수 없는 경우에는 null |
496 | */ |
497 | public Matrix invers() { |
498 |
499 | double[][] temp = new double[row][row]; |
500 | // temp=this.getMatrix()로 하면 레퍼런스로 되어서 본래 행렬이 |
501 | // 변경됨 |
502 | for (int i = 0; i < row; i++) { |
503 | for (int j = 0; j < row; j++) { |
504 | temp[i][j] = matrix[i][j]; |
505 | } |
506 | } |
507 | double[][] comp = Matrix.unitMatrix(col).getMatrix(); |
508 | for (int n = 0; n < col; n++) { |
509 | if (temp[n][n] == 0) // |
510 | { |
511 | for (int k = n; k < col; k++) { |
512 | if (temp[k][n] != 0) { |
513 | for (int a = 0; a < col; a++) { |
514 | comp[n][a] = comp[n][a] + comp[k][a]; |
515 | temp[n][a] = temp[n][a] + temp[k][a]; |
516 | } |
517 | break; |
518 | } |
519 | } |
520 | } |
521 | double p = temp[n][n]; |
522 | for (int a = 0; a < col; a++) { |
523 | comp[n][a] /= p; |
524 | temp[n][a] /= p; |
525 | } |
526 | for (int i = 0; i < col; i++) { |
527 | if (i != n) { |
528 | double p1 = temp[i][n]; |
529 | for (int j = col - 1; j >= 0; j--) { |
530 | comp[i][j] -= p1 * comp[n][j]; |
531 | temp[i][j] -= p1 * temp[n][j]; |
532 | } |
533 | } |
534 | } |
535 |
536 | } |
537 | Matrix tempReturn = new Matrix(comp); |
538 | if (multiply(tempReturn).equals(Matrix.unitMatrix(row))) { |
539 | // 만들어진 결과가 역행렬이 맞는지 확인 |
540 | return tempReturn; |
541 | } else { // 아닐경우 null리턴 |
542 | System.out.println("경고)역행렬이 존재하않는 행렬일수 있습니다."); |
543 | return null; |
544 | } |
545 |
546 | } |
547 |
548 | /** |
549 | * 왼쪽 나눗셈<br> |
550 |
551 |
552 |
553 | * 선형방정식의 해를 구할때 씀 this*X=temp, X=this'*temp 일때 |
554 | * X를 구할수있다. |
555 | * |
556 | * @param temp |
557 | * @return |
558 | */ |
559 | public Matrix leftDivision(Matrix temp) { |
560 |
561 | return this.invers().multiply(temp); |
562 | } |
563 |
564 | /** |
565 | * 수반행렬 |
566 | * |
567 | * @return |
568 | */ |
569 | public Matrix adjoint() { |
570 | double temp[][] = new double[row][col]; |
571 | for (int i = 0; i < row; i++) { |
572 | for (int j = 0; j < col; j++) { |
573 | temp[i][j] = cofactor(i, j); |
574 | } |
575 | } |
576 | return new Matrix(temp); |
577 | } |
578 |
579 | /** |
580 | * 행렬식 |
581 | * |
582 | * @return |
583 | */ |
584 | public double determinant() // 행렬식 |
585 | { |
586 | return Matrix.determinant(this); |
587 | } |
588 |
589 | public String size() |
590 | // 전채 크기를 String로 리턴 배열로 리턴하려했으나 조금 문제가 있음 |
591 | { |
592 | return row + " " + col; |
593 | } |
594 |
595 | /** |
596 | * |
597 | * @return Matrix의 배열을 리턴 |
598 | */ |
599 | public double[][] getMatrix() { |
600 | return matrix; |
601 | } |
602 |
603 | /** |
604 | * |
605 | * @return 행의 크기 |
606 | */ |
607 | public int getRowSize() { |
608 | return this.row; |
609 | } |
610 |
611 | /** |
612 | * |
613 | * @return 열의 크기 |
614 | */ |
615 | public int getColSize() { |
616 | return col; |
617 | } |
618 |
619 | /** |
620 | * 행렬의 덧셈 |
621 | * |
622 | * @param A |
623 | * 더해질 행렬 |
624 | * @return 현재 행렬에 A 를 더한 행렬 |
625 | */ |
626 |
627 | public Matrix plus(Matrix A) { |
628 |
629 | double[][] temp = Matrix.zeros(A.row, A.col).getMatrix(); |
630 | if (equalSize(A, this)) { |
631 | for (int i = 0; i < A.getRowSize(); i++) { |
632 | for (int k = 0; k < A.getColSize(); k++) { |
633 | temp[i][k] = A.matrix[i][k] + this.matrix[i][k]; |
634 | } |
635 | } |
636 | return new Matrix(temp); |
637 | } |
638 | return new Matrix(temp); |
639 | } |
640 |
641 | /** |
642 | * 행렬의 뺄셈 |
643 | * |
644 | * @param A |
645 | * 더해질 뺄셈 |
646 | * @return 현재 행렬에 A 를 뺀 행렬 |
647 | */ |
648 | public Matrix minus(Matrix A) { |
649 | // 행렬 뺄셈 |
650 | double[][] temp = Matrix.zeros(A.row, A.col).getMatrix(); |
651 | if (equalSize(A, this)) { |
652 | for (int i = 0; i < A.getRowSize(); i++) { |
653 | for (int k = 0; k < A.getColSize(); k++) { |
654 | temp[i][k] = A.matrix[i][k] - this.matrix[i][k]; |
655 | } |
656 | } |
657 | return new Matrix(temp); |
658 | } |
659 | return new Matrix(temp); |
660 | } |
661 |
662 | /** |
663 | * |
664 | * @param m |
665 | * 비교할 행렬 |
666 | * @return 현재 행렬과 m이 같으면 true |
667 | */ |
668 | public boolean equals(Matrix m) { |
669 | if (m.row == this.row && m.col == this.col) { |
670 | for (int i = 1; i < row; i++) { |
671 | for (int j = 1; j < col; j++) { |
672 | if (Math.abs(m.matrix[i][j] - this.matrix[i][j]) >= 0.0000001) { |
673 | // 컴퓨터로 계산한 값이기 때문에 두 값의 차가 |
674 | // 0.0000001 보다 작으면 같다고 볼수 있다. |
675 | // 행렬의 원소 자체가 매우 작으면 문제가 발생할수 |
676 | // 있으나 이경우는 무시하기로한다 |
677 | return false; |
678 | } |
679 | } |
680 | } |
681 | } |
682 | return true; |
683 | } |
684 | } |
'Programming > Algorithm' 카테고리의 다른 글
| 힙 정렬 - Heap Sort (0) | 2011.04.17 |
|---|---|
| 빠른 정렬 - QuickSort (0) | 2011.04.16 |
| 최대 힙 최소 힙 (0) | 2011.04.16 |
| 색종이 만들기 (0) | 2011.04.16 |
| Convex Hull Divide and Conquer for JAVA (0) | 2011.04.16 |