-
Notifications
You must be signed in to change notification settings - Fork 0
/
equation_solver.py
157 lines (137 loc) · 5.81 KB
/
equation_solver.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
import numpy as np
class LinearEquationSolver:
def __init__(self):
self.num_of_equations = 0
self.matrix = None
def getting_input(self):
self.num_of_equations = int(input())
matrix_of_equation = []
for _ in range(self.num_of_equations):
equation = list(map(int, input().split()))
matrix_of_equation.append(equation)
self.matrix = np.matrix(matrix_of_equation, dtype=np.float64)
def smallest_pivot_position(self, num_row):
position_of_pivots = []
for p in range(num_row, (self.matrix.shape[0])):
m = self.matrix[p].tolist()
index_first_match = next(
(index for index, item in enumerate(m[0])
if item != 0),
None
)
if index_first_match is None:
index_first_match = 100000000
if index_first_match < num_row:
continue
position_of_pivots.append((p, index_first_match))
return min(position_of_pivots, key=lambda tup: tup[1])
def greatest_pivot_position(self, num_row):
position_of_pivots = []
for p in range(num_row, -1, -1):
m = self.matrix[p].tolist()
index_first_match = next(
(index for index, item in enumerate(m[0])
if item != 0),
None
)
if index_first_match is None:
index_first_match = 100000000
position_of_pivots.append((p, index_first_match))
return max(position_of_pivots, key=lambda tup: tup[1])
def swap_rows(self, original_row, swapped_row):
temp = np.array(self.matrix[original_row], dtype=np.float64)
self.matrix[original_row] = self.matrix[swapped_row]
self.matrix[swapped_row] = temp
def rows_operations(self, row1, row2, operand):
self.matrix[row2] = self.matrix[row2] + self.matrix[row1] * operand
def row_reduce_1(self, row, operand):
self.matrix[row] = self.matrix[row] / operand
def pivot_finder(self):
position_of_pivots = []
for p in range(self.matrix.shape[0]):
m = self.matrix[p].tolist()
index_first_match = next(
(index for index, item in enumerate(m[0])
if item != 0),
None
)
if index_first_match is None:
continue
position_of_pivots.append((p, index_first_match))
return position_of_pivots
def equation_solver(self, position_of_pivots):
print('dafssssssss \n ', position_of_pivots)
for pivot in position_of_pivots:
answer = 0
for i in range(pivot[1] + 1, self.matrix.shape[1] - 1):
answer += self.matrix[pivot[0], i] * 10
final_answer = self.matrix[pivot[0], self.matrix.shape[1] - 1] - answer
print('x[{}] : {}'.format(pivot[1] + 1, final_answer))
for j in range(self.matrix.shape[1] - 1):
flag_in = False
for pivot in position_of_pivots:
if j == pivot[1]:
flag_in = True
if not flag_in:
print('x[{}] : 10'.format(j + 1))
def find_coefficient(self, i, pivot):
if self.matrix[pivot[0], pivot[1]] == 0:
return None
coefficient_f = -(self.matrix[i, pivot[1]] / self.matrix[pivot[0], pivot[1]])
print('coefficient_f ', coefficient_f)
return coefficient_f
def is_consistent(self):
for r in range(self.matrix.shape[0] - 1, -1, -1):
m = self.matrix[self.matrix.shape[0] - 1].tolist()
index_first_match = next(
(index for index, item in enumerate(m[0])
if item != 0),
None
)
if index_first_match == self.matrix.shape[1] - 1:
return False
return True
# forward
def forward_phase(self):
for r in range(self.matrix.shape[0] - 1):
pivot = self.smallest_pivot_position(r)
self.swap_rows(r, pivot[0])
pivot = self.smallest_pivot_position(r)
for i in range(pivot[0] + 1, self.matrix.shape[0]):
if pivot[1] == 100000000:
continue
coefficient = self.find_coefficient(i, pivot)
if coefficient is not None:
self.rows_operations(pivot[0], i, coefficient)
# backward
def backward_phase(self):
for r in range(self.matrix.shape[0] - 1, -1, -1):
pivot = self.greatest_pivot_position(r)
if pivot[1] == self.matrix.shape[1] - 1 and pivot[0] == self.matrix.shape[0] - 1:
continue
for i in range(pivot[0] - 1, -1, -1):
if pivot[1] == 100000000:
continue
coefficient = self.find_coefficient(i, pivot)
if coefficient is not None:
self.rows_operations(pivot[0], i, coefficient)
def reduced_echelon_form(self):
for r in range(self.matrix.shape[0] - 1):
pivot = self.smallest_pivot_position(r)
self.swap_rows(r, pivot[0])
for r in range(self.matrix.shape[0]):
pivot = self.smallest_pivot_position(r)
if pivot[1] == 100000000:
continue
if pivot[1] == self.matrix.shape[1] - 1 and pivot[0] == self.matrix.shape[0] - 1:
continue
self.row_reduce_1(pivot[0], self.matrix[pivot[0], pivot[1]])
def solve(self):
self.getting_input()
self.forward_phase()
self.backward_phase()
self.reduced_echelon_form()
print('Matrix is consistent: ', self.is_consistent())
self.equation_solver(self.pivot_finder())
linear_equaion_solver = LinearEquationSolver()
linear_equaion_solver.solve()