Z12-Rešenja

Table of Contents

  1. Zadatak 1

Zadatak 1

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
import sys
import random
import time

def random_list(values, elements):
    list = [random.choice(values) for _ in range(elements)]
    return list

def lcs(S, n, T, m):
    if n < 0 or m < 0:
        return 0
    if S[n] == T[m]:
        return 1 + lcs(S, n - 1, T, m - 1)
    else:
        return max(lcs(S, n - 1, T, m), lcs(S, n, T, m - 1))

def lcs_length(X, Y):
    m = len(X)
    n = len(Y)
    b = [[0 for i in range(n)] for j in range(m)]
    c = [[0 for i in range(n + 1)] for j in range(m + 1)]

    for i in range(m):
        for j in range(n):
            I = i + 1
            J = j + 1
            if X[i] == Y[j]:
                c[I][J] = c[I - 1][J - 1] + 1
                b[i][j] = Direction.UPLEFT
            elif c[I - 1][J] >= c[I][J - 1]:
                c[I][J] = c[I - 1][J - 1]
                b[i][j] = Direction.UP
            else:
                c[I][J] = c[I][J - 1]
                b[i][j] = Direction.LEFT
    return (c, b)

def print_lcs(b, X, i, j):
    if i < 0 or j < 0:
        return
    if b[i][j] == Direction.UPLEFT:
        print_lcs(b, X, i - 1, j - 1)
        print(X[i], end="")
    elif b[i][j] == Direction.UP:
        print_lcs(b, X, i - 1, j)
    else:
        print_lcs(b, X, i, j - 1)

class Direction:
    UP = "↑"
    LEFT = "←"
    UPLEFT = "↖"

def test_dynamic(i):
    l1 = random_list("ABCDEFGHIJKLMNOPQRSTUVWXZ", i)
    l2 = random_list("ABCDEFGHIJKLMNOPQRSTUVWXZ", i)

    start_time = time.clock()

    (c, b) = lcs_length(l1, l2)

    end_time = time.clock() - start_time

    print("Elements:", i, "Duration dynamic: ", end_time)

def test_iterative(i):
    l1 = random_list("ABCDEFGHIJKLMNOPQRSTUVWXZ", i)
    l2 = random_list("ABCDEFGHIJKLMNOPQRSTUVWXZ", i)

    start_time = time.clock()

    lcs(l1, len(l1) - 1, l2, len(l2) - 1)

    end_time = time.clock() - start_time

    print("Elements:", i, "Duration iterative: ", end_time)

if __name__ == "__main__":
    X = "BDCABA"
    Y = "ABCBDAB"
    print("X =", X)
    print("Y =", Y)
    n = lcs(X, len(X) - 1, Y, len(Y) - 1)
    print(n)

    (c, b) = lcs_length(X, Y)

    print_lcs(b, X, len(X) - 1, len(Y) - 1)
    print()

    # Test speed
    for i in [10, 50, 100, 500, 1000, 5000]:
        test_dynamic(i)

    for i in [5, 10, 11, 12, 13, 14, 15]:
        test_iterative(i)

zadatak1.py