algorithms

committed 0ffedd8

initial

`+*.pyc`
`+.idea`

common.py

`+# -*- coding:utf-8 -*-`
`+from decimal import Decimal`
`+`
`+`
`+def get_equations():`
`+    in_str = True`
`+    matrix = []`
`+    while in_str:`
`+        in_str = raw_input('Enter arguments of equation: ')`
`+        if in_str:`
`+            matrix.append(map(Decimal, in_str.split()))`
`+    return matrix`
`+`
`+`
`+def print_matrix(m):`
`+    """`
`+    Prints given matrix`
`+`
`+    >>> print_matrix([[4, 2, 3, 1], [0, 8, 9, 6], [8, 6, 7, 5]])`
`+      4.0000  2.0000  3.0000  1.0000`
`+      0.0000  8.0000  9.0000  6.0000`
`+      8.0000  6.0000  7.0000  5.0000`
`+    ----------------------------------`
`+    """`
`+    for line in m:`
`+        print ''.join(map(lambda s: '{: >8.4f}'.format(s), line))`
`+    print('-' * 34)`
`+`
`+`
`+if __name__ == "__main__":`
`+    import doctest`
`+    doctest.testmod()`

gauss.py

`+# -*- coding:utf-8 -*-`
`+from copy import deepcopy`
`+from decimal import Decimal`
`+from common import get_equations, print_matrix`
`+from krammer import determinant`
`+`
`+`
`+def swap_lines(matrix, line_number1, line_number2):`
`+    """`
`+    >>> m = [[Decimal(2), Decimal(3), Decimal(1), Decimal(2)],`
`+    ... [Decimal(2), Decimal(0), Decimal(4), Decimal(1)],`
`+    ... [Decimal(4), Decimal(-1), Decimal(1), Decimal(3)]]`
`+    >>> print_matrix(m)`
`+      2.0000  3.0000  1.0000  2.0000`
`+      2.0000  0.0000  4.0000  1.0000`
`+      4.0000 -1.0000  1.0000  3.0000`
`+    ----------------------------------`
`+    >>> swapped = swap_lines(m, 0, 1)`
`+    >>> print_matrix(swapped)`
`+      2.0000  0.0000  4.0000  1.0000`
`+      2.0000  3.0000  1.0000  2.0000`
`+      4.0000 -1.0000  1.0000  3.0000`
`+    ----------------------------------`
`+    """`
`+    _matrix = deepcopy(matrix)`
`+    _matrix[line_number1], _matrix[line_number2] = _matrix[line_number2], _matrix[line_number1]`
`+    return _matrix`
`+`
`+`
`+def multiply_line(matrix, line_number, multiplier):`
`+    """`
`+    >>> m = [[Decimal(2), Decimal(3), Decimal(1), Decimal(2)],`
`+    ... [Decimal(2), Decimal(0), Decimal(4), Decimal(1)],`
`+    ... [Decimal(4), Decimal(-1), Decimal(1), Decimal(3)]]`
`+    >>> print_matrix(m)`
`+      2.0000  3.0000  1.0000  2.0000`
`+      2.0000  0.0000  4.0000  1.0000`
`+      4.0000 -1.0000  1.0000  3.0000`
`+    ----------------------------------`
`+    >>> multiplied = multiply_line(m, 0, 3)`
`+    >>> print_matrix(multiplied)`
`+      6.0000  9.0000  3.0000  6.0000`
`+      2.0000  0.0000  4.0000  1.0000`
`+      4.0000 -1.0000  1.0000  3.0000`
`+    ----------------------------------`
`+    """`
`+    _matrix = deepcopy(matrix)`
`+    _matrix[line_number] = map(lambda i: i * multiplier, _matrix[line_number])`
`+    return _matrix`
`+`
`+`
`+def add_line(matrix, line_to_add_number, line_to_be_added_number, with_multiplier=1):`
`+    """`
`+    >>> m = [[Decimal(2), Decimal(3), Decimal(1), Decimal(2)],`
`+    ... [Decimal(2), Decimal(0), Decimal(4), Decimal(1)],`
`+    ... [Decimal(4), Decimal(-1), Decimal(1), Decimal(3)]]`
`+    >>> print_matrix(m)`
`+      2.0000  3.0000  1.0000  2.0000`
`+      2.0000  0.0000  4.0000  1.0000`
`+      4.0000 -1.0000  1.0000  3.0000`
`+    ----------------------------------`
`+    >>> added1 = add_line(m, 0, 2)`
`+    >>> print_matrix(added1)`
`+      6.0000  2.0000  2.0000  5.0000`
`+      2.0000  0.0000  4.0000  1.0000`
`+      4.0000 -1.0000  1.0000  3.0000`
`+    ----------------------------------`
`+    >>> print_matrix(m)  # must not be changed`
`+      2.0000  3.0000  1.0000  2.0000`
`+      2.0000  0.0000  4.0000  1.0000`
`+      4.0000 -1.0000  1.0000  3.0000`
`+    ----------------------------------`
`+    >>> added2 = add_line(m, 0, 2, 2)`
`+    >>> print_matrix(added2)`
`+     10.0000  1.0000  3.0000  8.0000`
`+      2.0000  0.0000  4.0000  1.0000`
`+      4.0000 -1.0000  1.0000  3.0000`
`+    ----------------------------------`
`+    """`
`+    _matrix = deepcopy(matrix)`
`+    _matrix[line_to_add_number] = map(sum, zip(_matrix[line_to_add_number],`
`+                                               map(lambda i: i * with_multiplier, _matrix[line_to_be_added_number])))`
`+    return _matrix`
`+`
`+`
`+def gauss(matrix):`
`+    """`
`+    >>> m1 = [[Decimal(2), Decimal(3), Decimal(1), Decimal(2)],`
`+    ... [Decimal(2), Decimal(0), Decimal(4), Decimal(1)],`
`+    ... [Decimal(4), Decimal(-1), Decimal(1), Decimal(3)]]`
`+    >>> gauss(m1)`
`+    [Decimal('0.8333333333333333333333333335'), Decimal('0.1666666666666666666666666668'), Decimal('-0.1666666666666666666666666667')]`
`+`
`+    >>> m2 = [[Decimal(2), Decimal(3), Decimal(1), Decimal(2)],`
`+    ... [Decimal(4), Decimal(-1), Decimal(1), Decimal(3)],`
`+    ... [Decimal(2), Decimal(0), Decimal(4), Decimal(1)]]`
`+    >>> gauss(m2)`
`+    [Decimal('0.833333333333333333333333333'), Decimal('0.166666666666666666666666667'), Decimal('-0.1666666666666666666666666667')]`
`+    """`
`+    m = deepcopy(matrix)`
`+    # prepare line 2:`
`+    k1 = - (m[1][0] / m[2][0])`
`+    m = add_line(m, 1, 2, k1)`
`+`
`+    k0 = - (m[2][0] / m[0][0])`
`+    m = add_line(m, 2, 0, k0)`
`+`
`+    k2 = - (m[2][1] / m[1][1])`
`+    m = add_line(m, 2, 1, k2)`
`+`
`+    x2 = m[2][3] / m[2][2]`
`+    x1 = (m[1][3] - m[1][2] * x2) / m[1][1]`
`+    x0 = (m[0][3] - m[0][1] * x1 - m[0][2] * x2) / m[0][0]`
`+    return [x0, x1, x2]`
`+`
`+`
`+if __name__ == '__main__':`
`+    matrix = get_equations()`
`+`
`+    print gauss(matrix)`
`+`

krammer.py

`+# -*- coding:utf-8 -*-`
`+from copy import deepcopy`
`+from decimal import Decimal`
`+from common import get_equations`
`+`
`+`
`+def replace_column(m, column_number):`
`+    """`
`+    Replaces column column_number with the last column`
`+    """`
`+    out_matrix = deepcopy(m)`
`+    for line in out_matrix:`
`+        line[column_number] = line[-1]`
`+    return out_matrix`
`+`
`+`
`+def determinant(m):`
`+    """`
`+    Returns Determinant of 2 or 3-dimentional matrix`
`+`
`+    >>> determinant([[2, 4], [3, 3]])`
`+    -6`
`+    >>> determinant([[7, 4], [1, 3]])`
`+    17`
`+    >>> determinant([[2, 3, 1], [2, 0, 4], [4, -1, 1]])`
`+    48`
`+    >>> determinant([[2, 3, 1], [1, 0, 4], [3, -1, 1]])`
`+    40`
`+    >>> determinant([[2, 2, 1], [2, 1, 4], [4, 3, 1]])`
`+    8`
`+    >>> determinant([[2, 3, 2], [2, 0, 1], [4, -1, 3]])`
`+    -8`
`+    """`
`+    if len(m) == 2:`
`+        return m[0][0] * m[1][1] - m[0][1] * m[1][0]`
`+    else:`
`+        return m[0][0] * m[1][1] * m[2][2] +\`
`+               m[2][0] * m[0][1] * m[1][2] +\`
`+               m[0][2] * m[1][0] * m[2][1] -\`
`+               m[2][0] * m[1][1] * m[0][2] -\`
`+               m[0][0] * m[2][1] * m[1][2] -\`
`+               m[1][0] * m[0][1] * m[2][2]`
`+`
`+`
`+def krammer(_matrix):`
`+    """`
`+    >>> m = [[Decimal(2), Decimal(3), Decimal(1), Decimal(2)],`
`+    ... [Decimal(2), Decimal(0), Decimal(4), Decimal(1)],`
`+    ... [Decimal(4), Decimal(-1), Decimal(1), Decimal(3)]]`
`+    >>> krammer(m)`
`+    D = 48.000000`
`+    [Decimal('0.8333333333333333333333333333'), Decimal('0.1666666666666666666666666667'), Decimal('-0.1666666666666666666666666667')]`
`+    """`
`+    _determinant = determinant(_matrix)`
`+    if _determinant == 0:`
`+        raise Exception('No or infinity solutions')`
`+    print('D = %f' % _determinant)`
`+    return [determinant(replace_column(_matrix, l)) / _determinant for l in range(len(_matrix))]`
`+`
`+`
`+if __name__ == '__main__':`
`+    matrix = get_equations()`
`+`
`+    x_list = krammer(matrix)`
`+    for i, x in enumerate(x_list):`
`+        print('x%s = %f' % (i, x))`
`+`
`+`
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.