Алгоритмы и структуры данных на Python

Алгоритмы и структуры данных на Python с примерами кода

Алгоритм Кнута-Морриса-Пратта (КМП-алгоритм) | Алгоритмы на Python

t = "лилила"

p = [0]*len(t)
j = 0
i = 1

while i < len(t):
    if t[j] == t[i]:
        p[i] = j+1
        i += 1
        j += 1
    else:
        if j == 0:
            p[i] = 0;
            i += 1
        else:
            j = p[j-1]

print(p)

a = "лилилось лилилась"
m = len(t)
n = len(a)

i = 0
j = 0
while i < n:
    if a[i] == t[j]:
        i += 1
        j += 1
        if j == m:
            print("образ найден")
            break
    else:
        if j > 0:
            j = p[j-1]
        else:
            i += 1

if i == n and j != m:
    print("образ не найден")

Алгоритм Бойера-Мура-Хорспула | Алгоритмы на Python

t = "данные"

# Этап 1: формирование таблицы смещений

S = set()  # уникальные символы в образе
M = len(t) # число символов в образе
d = {}     # словарь смещений

for i in range(M-2, -1, -1): # итерации с предпоследнего символа
    if t[i] not in S:        # если символ еще не добавлен в таблицу
        d[t[i]] = M-i-1
        S.add(t[i])

if t[M-1] not in S:     # отдельно формируем последний символ
    d[t[M-1]] = M

d['*'] = M              # смещения для прочих символов

print(d)

# Этап 2: поиск образа в строке

a = "метеоданные"
N = len(a)

if N >= M:
    i = M-1       # счетчик проверяемого символа в строке

    while(i < N):
        k = 0
        j = 0
        flBreak = False
        for j in range(M-1, -1, -1):
            if a[i-k] != t[j]:
                if j == M-1:
                    off = d[a[i]] if d.get(a[i], False) else d['*']  # смещение, если не равен последний символ образа
                else:
                    off = d[t[j]]   # смещение, если не равен не последний символ образа

                i += off    # смещение счетчика строки
                flBreak = True  # если несовпадение символа, то flBreak = True
                break

            k += 1          # смещение для сравниваемого символа в строке

        if not flBreak:          # если дошли до начала образа, значит, все его символы совпали
            print(f"образ найден по индексу {i-k+1}")
            break
    else:
        print("образ не найден")
else:
    print("образ не найден")

Алгоритм Дейкстры (Dijkstra’s algorithm) | Алгоритмы на Python

import math


def arg_min(T, S):
    amin = -1
    m = math.inf  # максимальное значение
    for i, t in enumerate(T):
        if t < m and i not in S:
            m = t
            amin = i

    return amin


D = ((0, 3, 1, 3, math.inf, math.inf),
     (3, 0, 4, math.inf, math.inf, math.inf),
     (1, 4, 0, math.inf, 7, 5),
     (3, math.inf, math.inf, 0, math.inf, 2),
     (math.inf, math.inf, 7, math.inf, 0, 4),
     (math.inf, math.inf, 5, 2, 4, 0))

N = len(D)  # число вершин в графе
T = [math.inf]*N   # последняя строка таблицы

v = 0       # стартовая вершина (нумерация с нуля)
S = {v}     # просмотренные вершины
T[v] = 0    # нулевой вес для стартовой вершины
M = [0]*N   # оптимальные связи между вершинами

while v != -1:          # цикл, пока не просмотрим все вершины
    for j, dw in enumerate(D[v]):   # перебираем все связанные вершины с вершиной v
        if j not in S:           # если вершина еще не просмотрена
            w = T[v] + dw
            if w < T[j]:
                T[j] = w
                M[j] = v        # связываем вершину j с вершиной v

    v = arg_min(T, S)            # выбираем следующий узел с наименьшим весом
    if v >= 0:                    # выбрана очередная вершина
        S.add(v)                 # добавляем новую вершину в рассмотрение

#print(T, M, sep="\n")

# формирование оптимального маршрута:
start = 0
end = 4
P = [end]
while end != start:
    end = M[P[-1]]
    P.append(end)

print(P)

Алгоритм Флойда (Floyd’s algorithm) | Алгоритмы на Python

import math


def get_path(P, u, v):
    path = [u]
    while u != v:
        u = P[u][v]
        path.append(u)

    return path


V = [[0, 2, math.inf, 3, 1, math.inf, math.inf, 10],
     [2, 0, 4, math.inf, math.inf, math.inf, math.inf, math.inf],
     [math.inf, 4, 0, math.inf, math.inf, math.inf, math.inf, 3],
     [3, math.inf, math.inf, 0, math.inf, math.inf, math.inf, 8],
     [1, math.inf, math.inf, math.inf, 0, 2, math.inf, math.inf],
     [math.inf, math.inf, math.inf, math.inf, 2, 0, 3, math.inf],
     [math.inf, math.inf, math.inf, math.inf, math.inf, 3, 0, 1],
     [10, math.inf, 3, 8, math.inf, math.inf, 1, 0],
]

N = len(V)                       # число вершин в графе
P = [[v for v in range(N)] for u in range(N)]       # начальный список предыдущих вершин для поиска кратчайших маршрутов

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = V[i][k] + V[k][j]
            if V[i][j] > d:
                V[i][j] = d
                P[i][j] = k     # номер промежуточной вершины при движении от i к j

# нумерацця вершин начинается с нуля
start = 1
end = 4
print(get_path(P, end, start))

Алгоритм Форда-Фалкерсона | Алгоритмы на Python

import math


def get_max_vertex(k, V, S):
    m = 0   # наименьшее допустимое значение
    v = -1
    for i, w in enumerate(V[k]):
        if i in S:
            continue

        if w[2] == 1:   # движение по стрелке
            if m < w[0]:
                m = w[0]
                v = i
        else:           # движение против стрелки
            if m < w[1]:
                m = w[1]
                v = i

    return v


def get_max_flow(T):
    w = [x[0] for x in T]
    return min(*w)


def updateV(V, T, f):
    for t in T:
        if t[1] == -1:  # это исток
            continue

        sgn = V[t[2]][t[1]][2]  # направление движения

        # меняем веса в таблице для (i,j) и (j,i)
        V[t[1]][t[2]][0] -= f * sgn
        V[t[1]][t[2]][1] += f * sgn

        V[t[2]][t[1]][0] -= f * sgn
        V[t[2]][t[1]][1] += f * sgn


V = [[[0,0,1], [20,0,1], [30,0,1], [10,0,1], [0,0,1]],
     [[20,0,-1], [0,0,1], [40,0,1], [0,0,1], [30,0,1]],
     [[30,0,-1], [40,0,-1], [0,0,1], [10,0,1], [20,0,1]],
     [[10,0,-1], [0,0,1], [10,0,-1], [0,0,1], [20,0,1]],
     [[0,0,1], [30,0,-1], [20,0,-1], [20,0,-1], [0,0,1]],
]

N = len(V)  # число вершин в графе
init = 0    # вершина истока (нумерация с нуля)
end = 4     # вершина стока
Tinit = (math.inf, -1, init)      # первая метка маршруто (a, from, vertex)
f = []      # максимальные потоки найденных маршрутов

j = init
while j != -1:
    k = init  # стартовая вершина (нумерация с нуля)
    T = [Tinit]  # метки маршрута
    S = {init}  # множество просмотренных вершин

    while k != end:     # пока не дошли до стока
        j = get_max_vertex(k, V, S)  # выбираем вершину с наибольшей пропускной способностью
        if j == -1:         # если следующих вершин нет
            if k == init:      # и мы на истоке, то
                break          # завершаем поиск маршрутов
            else:           # иначе, переходим к предыдущей вершине
                k = T.pop()[2]
                continue

        c = V[k][j][0] if V[k][j][2] == 1 else V[k][j][1]   # определяем текущий поток
        T.append((c, j, k))    # добавляем метку маршрута
        S.add(j)            # запоминаем вершину как просмотренную

        if j == end:    # если дошди до стока
            f.append(get_max_flow(T))     # находим максимальную пропускную способность маршрута
            updateV(V, T, f[-1])        # обновляем веса дуг
            break

        k = j

F = sum(f)
print(f"Максимальный поток равен: {F}")

Алгоритм Краскала (Kruskal’s algorithm) | Алгоритмы на Python

#-------------------------------------------------
# Алгоритм Краскала поиска минимального остова графа
#-------------------------------------------------

# список ребер графа (длина, вершина 1, вершина 2)
R = [(13, 1, 2), (18, 1, 3), (17, 1, 4), (14, 1, 5), (22, 1, 6),
     (26, 2, 3), (22, 2, 5), (3, 3, 4), (19, 4, 6)]

Rs = sorted(R, key=lambda x: x[0])
U = set()   # список соединенных вершин
D = {}      # словарь списка изолированных групп вершин
T = []      # список ребер остова

for r in Rs:
    if r[1] not in U or r[2] not in U:  # проверка для исключения циклов в остове
        if r[1] not in U and r[2] not in U: # если обе вершины не соединены, то
            D[r[1]] = [r[1], r[2]]          # формируем в словаре ключ с номерами вершин
            D[r[2]] = D[r[1]]               # и связываем их с одним и тем же списком вершин
        else:                           # иначе
            if not D.get(r[1]):             # если в словаре нет первой вершины, то
                D[r[2]].append(r[1])        # добавляем в список первую вершину
                D[r[1]] = D[r[2]]           # и добавляем ключ с номером первой вершины
            else:
                D[r[1]].append(r[2])        # иначе, все то же самое делаем со второй вершиной
                D[r[2]] = D[r[1]]

        T.append(r)             # добавляем ребро в остов
        U.add(r[1])             # добавляем вершины в множество U
        U.add(r[2])

for r in Rs:    # проходим по ребрам второй раз и объединяем разрозненные группы вершин
    if r[2] not in D[r[1]]:     # если вершины принадлежат разным группам, то объединяем
        T.append(r)             # добавляем ребро в остов
        gr1 = D[r[1]]
        D[r[1]] += D[r[2]]      # объединем списки двух групп вершин
        D[r[2]] += gr1

print(T)

Алгоритм Прима (ближайшего соседа) | Алгоритмы на Python

#-------------------------------------------------
# Алгоритм Прима поиска минимального остова графа
#-------------------------------------------------
import math


def get_min(R, U):
    rm = (math.inf, -1, -1)
    for v in U:
        rr = min(R, key=lambda x: x[0] if (x[1] == v or x[2] == v) and (x[1] not in U or x[2] not in U) else math.inf)
        if rm[0] > rr[0]:
            rm = rr

    return rm


# список ребер графа (длина, вершина 1, вершина 2)
# первое значение возвращается, если нет минимальных ребер
R = [(math.inf, -1, -1), (13, 1, 2), (18, 1, 3), (17, 1, 4), (14, 1, 5), (22, 1, 6),
     (26, 2, 3), (19, 2, 5), (30, 3, 4), (22, 4, 6)]

N = 6     # число вершин в графе
U = {1}   # множество соединенных вершин
T = []    # список ребер остова

while len(U) < N:
    r = get_min(R, U)       # ребро с минимальным весом
    if r[0] == math.inf:    # если ребер нет, то остов построен
        break

    T.append(r)             # добавляем ребро в остов
    U.add(r[1])             # добавляем вершины в множество U
    U.add(r[2])

print(T)

Сортировка выбором | Алгоритмы на Python

#-------------------------------------------------
# Алгоритм сортировки выбором
#-------------------------------------------------

a = [-3, 5, 0, -8, 1, 10]
N = len(a)      # число элементов в списке

for i in range(N-1):
    m = a[i]            # запоминаем минимальное значение
    p = i               # запоминаем индекс минимального значения
    for j in range(i+1, N):  # поиск миимального среди оставшихся элементов
        if m > a[j]:
            m = a[j]
            p = j

    if p != i:          # обмен значениями, если был найден минимальный не в i-й позиции
        t = a[i]
        a[i] = a[p]
        a[p] = t

print(a)

Сортировка вставками | Алгоритмы на Python

#-------------------------------------------------
# Алгоритм сортировки вставками
#-------------------------------------------------

a = [-3, 5, 0, -8, 1, 10]
N = len(a)      # число элементов в списке

for i in range(1, N):
    for j in range(i, 0, -1):
        if a[j] < a[j-1]:
            a[j], a[j-1] = a[j-1], a[j]
        else:
            break

print(a)

Сортировка пузырьком (метод всплывающего пузырька) | Алгоритмы на Python

#-------------------------------------------------
# Алгоритм сортировки пузырьком
#-------------------------------------------------

a = [7, 5, -8, 0, 10, 1]
N = len(a)      # число элементов в списке

for i in range(0, N-1):     # N-1 итераций работы алгоритма
    for j in range(0, N-1-i):   # проход по оставшимся не отсортированным парам массива
        if a[j] > a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]

print(a)

Слияние двух упорядоченных списков | Алгоритмы на Python

#-------------------------------------------------
# Метод слияния двух списков
#-------------------------------------------------

a = [1, 4, 10, 11]
b = [2, 3, 3, 4, 8]
c = []

N = len(a)
M = len(b)

i = 0
j = 0
while i < N and j < M:
    if a[i] <= b[j]:
        c.append(a[i])
        i += 1
    else:
        c.append(b[j])
        j += 1

c += a[i:] + b[j:]

# if i < N:
#     for k in range(i, N):
#         c.append(a[k])
# elif j < M:
#     for k in range(j, M):
#         c.append(b[k])

print(c)

Быстрая сортировка слиянием (merge sort) | Алгоритмы на Python

#-------------------------------------------------
# Сортировка слиянием
#-------------------------------------------------

# функция слияния двух отсортированных списков
def merge_list(a, b):
    c = []
    N = len(a)
    M = len(b)

    i = 0
    j = 0
    while i < N and j < M:
        if a[i] <= b[j]:
            c.append(a[i])
            i += 1
        else:
            c.append(b[j])
            j += 1

    c += a[i:] + b[j:]
    return c

# функция деления списка и слияния списков в общий отсортированный список
def split_and_merge_list(a):
    N1 = len(a) // 2
    a1 = a[:N1]     # деление массива на два примерно равной длины
    a2 = a[N1:]

    if len(a1) > 1: # если длина 1-го списка больше 1, то делим дальше
        a1 = split_and_merge_list(a1)
    if len(a2) > 1: # если длина 2-го списка больше 1, то делим дальше
        a2 = split_and_merge_list(a2)

    return merge_list(a1, a2)   # слияние двух отсортированных списков в один


a = [9, 5, -3, 4, 7, 8, -8]
a = split_and_merge_list(a)

print(a)

Быстрая сортировка Хоара | Алгоритмы на Python

#-------------------------------------------------
# Быстрая сортировка Хоара через рекурсию
#-------------------------------------------------
import random


def quick_sort(a):
    if len(a) > 1:
        x = a[random.randint(0, len(a)-1)]      # случайное пороговое значение (для разделения на малые и большие)
        low = [u for u in a if u < x]
        eq = [u for u in a if u == x]
        hi = [u for u in a if u > x]
        a = quick_sort(low) + eq + quick_sort(hi)

    return a


a = [9, 5, -3, 4, 7, 8, -8]
a = quick_sort(a)

print(a)

Стек типа LIFO (Last-In-First-Out) | Алгоритмы на Python

# Пример использования стека типа LIFO

a = input("Введите строку: ")
stack = []
flVerify = True

for lt in a:
    if lt in "([{":
        stack.append(lt)
    elif lt in ")]}":
        if len(stack) == 0:
            flVerify = False
            break

        br = stack.pop()
        if br == '(' and lt == ')':
            continue
        if br == '[' and lt == ']':
            continue
        if br == '{' and lt == '}':
            continue

        flVerify = False
        break

if flVerify and len(stack) == 0:    # стек по итогам проверок должен быть пустым
    print("Yes")
else:
    print("No")

Делаем очередь (queue) | Алгоритмы на Python

Возможно вам будет интересно:

Алгоритмы сортировки 26 видов

Алгоритмы и структуры данных