Интерактивная визуализация алгоритмов на базе Jupyter

from IPython.display import Codeimport randomdef qsort_state(array, left, right, x, p, q):    extended_array = list(map(str, array[:left])) + ['['] + list(map(str, array[left: right])) + [']'] + list(map(str, array[right:]))    offset_x = sum(list(map(len, extended_array[:left]))) + left + 2    zero_line = ''.join([' ' for i in range(offset_x)]) + f'x = {x}'    first_line = ' '.join(extended_array)    offset_p = sum(list(map(len, extended_array[:p + 1]))) + p + 1 + len(extended_array[p + 1]) // 2    offset_q = sum(list(map(len, extended_array[:q + 1]))) + q + 1 + len(extended_array[q + 1]) // 2    second_line = ''.join([' ' if i != offset_p and i != offset_q else '' for i in range(len(first_line))])    return Code(zero_line + '\n' + first_line + '\n' + second_line)def qsort(array, left, right, states):    if right - left <= 1:        return    x = array[random.randint(left, right - 1)]    p = left    q = right - 1    states.append(qsort_state(array, left, right, x, p, q))    while p <= q:        while array[p] < x:            p += 1            states.append(qsort_state(array, left, right, x, p, q))        while array[q] > x:            q -= 1            states.append(qsort_state(array, left, right, x, p, q))        if p <= q:            array[p], array[q] = (array[q], array[p])            states.append(qsort_state(array, left, right, x, p, q))            p += 1            q -= 1            if p <= q:                states.append(qsort_state(array, left, right, x, p, q))    qsort(array, left, q + 1, states)    qsort(array, p, right, states)  

a = [234, 1, 42, 3, 15, 3, 10, 9, 2]states = []qsort(a, 0, len(a), states)animate_list(states, play=True);

def bs_state(array, left, right, x):    extended_array = list(map(str, array[:left])) + ['['] + list(map(str, array[left: right])) + [']'] + list(map(str, array[right:]))     mid = (left + right) // 2    offset_x = sum(list(map(len, extended_array[:mid + 1]))) + mid + 1    return Code(' '.join(extended_array) + '\n' + ''.join([' ' for i in range(offset_x)]) + str(x))# Эта версия бинарного поиска находит последний элемент, который# меньше или равен искомогоstates = []left = 0right = len(a)x = 14while right - left > 1:    states.append(bs_state(a, left, right, x))    mid = (left + right) // 2    if a[mid] <= x:        left = mid    else:        right = midstates.append(bs_state(a, left, right, x))animate_list(states, play=True, interval=400);

def prefix_function_state(s, p, k, intermidiate=False):    third_string = ''.join([s[i] if i < k else ' ' for i in range(len(p))])    fourth_string = ''.join([s[i] if i >= len(p) - k else ' ' for i in range(len(p))])    return Code(s + '\n' + ''.join(list(map(str, (p + ['*'] if intermidiate else p )))) \                  + '\n' + third_string + '\n' + fourth_string)def prefix_function(s, states):    p = [0]    k = 0    states.append(prefix_function_state(s, p, k))    for letter in s[1:]:        states.append(prefix_function_state(s, p, k, True))        while k > 0 and s[k] != letter:            k = p[k - 1]            states.append(prefix_function_state(s, p, k, True))        if s[k] == letter:            k += 1        p.append(k)        states.append(prefix_function_state(s, p, k))    return pstates = []p = prefix_function('ababadababa', states)animate_list(states, play=True);

import numpy as npimport matplotlib.pyplot as plt# Функция, которую минимизируем, минимум в точке (0, 0)def f(x, y):    return 1.3 * (x - y) ** 2 + 0.7 * (x + y) ** 2# Отрисовка траектории и линий уровня функцииdef plot_trajectory(func, traj, limit_point=None):    fig = plt.figure(figsize=(7, 7))    ax = fig.add_axes([0, 0, 1, 1])            if limit_point:        ax.plot([limit_point[0]], [limit_point[1]], 'o', color='green')    #Level contours    delta = 0.025    x = np.arange(-2, 2, delta)    y = np.arange(-2, 2, delta)    X, Y = np.meshgrid(x, y)    Z = np.zeros_like(X)    for i in range(X.shape[0]):        for j in range(X.shape[1]):            Z[i][j] = func(X[i][j], Y[i][j])    CS = ax.contour(X, Y, Z, [0.5, 1.5, 3], colors=['blue', 'purple', 'red'])    ax.plot([u[0] for u in traj], [u[1] for u in traj], color='black')    ax.plot([u[0] for u in traj], [u[1] for u in traj], 'o', color='black')        plt.close(fig)    return figx, y = (1.0, 1.0)num_iters = 50trajectory = [(x, y)]plots = []# Итерируемся и сохраняем текущий путь на каждом шагеfor i in range(num_iters):    angle = 2 * np.pi * np.random.rand(1)    dx, dy = (np.cos(angle) / 2 / (i + 1) ** 0.5, np.sin(angle) / 2 / (i + 1) ** 0.5)    trajectory.append((x + dx, y + dy))    plots.append(plot_trajectory(f, trajectory, limit_point=(0, 0)))    if f(x, y) > f(x + dx, y + dy):        x = x + dx        y = y + dy    else:        trajectory = trajectory[:-1]animate_list(plots, play=True, interval=300);

# Данные можно взять например здесь# http://www.stat.cmu.edu/~larry/all-of-statistics/=data/faithful.datdata = []with open('data/faithful.csv') as f:    for line in f:        _, x, y = line.split(',')        try:            data.append((float(x), float(y)))        except ValueError:            passcolors = ['red', 'blue', 'yellow', 'green']# За основу взято https://jakevdp.github.io/PythonDataScienceHandbook/05.12-gaussian-mixtures.htmlfrom matplotlib.patches import Ellipsedef draw_ellipse(position, covariance, ax=None, **kwargs):    """Draw an ellipse with a given position and covariance"""    ax = ax or plt.gca()        # Convert covariance to principal axes    if covariance.shape == (2, 2):        U, s, Vt = np.linalg.svd(covariance)        angle = np.degrees(np.arctan2(U[1, 0], U[0, 0]))        width, height = 2 * np.sqrt(s)    else:        angle = 0        width, height = 2 * np.sqrt(covariance)        # Draw the Ellipse    for nsig in range(1, 4):        ax.add_patch(Ellipse(position, nsig * width, nsig * height,                             angle, color='red', **kwargs))        def plot_gmm(gmm, X, label=True, ax=None):    ax = ax or plt.gca()    if label:        labels = gmm.predict(X)        ax.scatter(X[:, 0], X[:, 1], c=labels, s=20, cmap='plasma', zorder=2)    else:        ax.scatter(X[:, 0], X[:, 1], s=20, zorder=2)        w_factor = 0.2 / gmm.weights_.max()    for pos, covar, w in zip(gmm.means_, gmm.covariances_, gmm.weights_):        draw_ellipse(pos, covar, alpha=w * w_factor)        def step_figure(gmm, X, label=True):    fig = plt.figure(figsize=(7, 7))    ax = fig.add_axes([0, 0, 1, 1])    ax.set_ylim(30, 100)    ax.set_xlim(1, 6)    plot_gmm(gmm, X, label=True, ax=ax)    plt.close(fig)    return figfrom sklearn.mixture import GaussianMixturex = np.array(data)# max_iters=1 и warm_start=True заставляют gmm.fit делать ровно одну итерацию# и сохранять состояниеgmm = GaussianMixture(2, warm_start=True, init_params='random', max_iter=1)# GMM выдает предупреждения на то, что одной итерации малоimport warnings warnings.simplefilter('ignore')# Инициализируем на небольшой порции данныхgmm.fit(x[:10,:])steps = [step_figure(gmm, x)]   for i in range(17):    gmm.fit(x)    steps.append(step_figure(gmm, x))animate_list(steps, play=True, interval=400);

# Обертка над matplotlib для отрисовки прямоугольника, разделенного на квадраты разных цветовfrom animation_utils.matplotlib import draw_fillingdef check_valid(i, j, n, m, tiling):    return 0 <= i and i < n and 0 <= j and j < m and tiling[i][j] != '#'def find_augmenting_path(x, y, n, m, visited, matched, tiling):    if not check_valid(x, y, n, m, tiling):        return False    if (x, y) in visited:        return False    visited.add((x, y))        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:        if not check_valid(x + dx, y + dy, n, m, tiling):            continue        if (x + dx, y + dy) not in matched or find_augmenting_path(*matched[(x + dx , y + dy)], n, m, visited, matched, tiling):            matched[(x + dx, y + dy)] = (x, y)            return True    return Falsedef convert_match(matched, tiling, n, m):    result = [[-1 if tiling[i][j] == '#' else -2 for j in range(m)] for i in range(n)]    num = 0    for x, y in matched:        _x, _y = matched[(x, y)]        result[x][y] = num        result[_x][_y] = num        num += 1    return resultdef match_with_flow(tiling):    result_slices = []    n = len(tiling)    m = len(tiling[0])        matched = dict()    # Для наглядности визуализации    rows = list(range(n))    columns = list(range(m))    random.shuffle(rows)    random.shuffle(columns)    result_slices.append(convert_match(matched, tiling, n, m))                for i in rows:        for j in columns:            if (i + j) % 2 == 1:                continue            visited = set()            if find_augmenting_path(i, j, n, m, visited, matched, tiling):                result_slices.append(convert_match(matched, tiling, n, m))                return result_slicestiling_custom=[    '...####',    '....###',    '......#',    '#.#....',    '#......',    '##.....',    '###...#',]sequencial_match = match_with_flow(tiling_custom)animate_list(list(map(draw_filling, sequencial_match)), play=True);

def color_5(filling):    result = [[i for i in row] for row in filling]    # Строим граф    domino_tiles = [[] for i in range(max(map(max, filling)) + 1)]    domino_neighbours = [set() for i in range(max(map(max, filling)) + 1)]    degree = [0 for i in range(max(map(max, filling)) + 1)]        n = len(filling)    m = len(filling[0])        for i, row in enumerate(filling):        for j, num in enumerate(row):            if num >= 0:                domino_tiles[num].append((i, j))                    for i, tiles in enumerate(domino_tiles):        for x, y in tiles:            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]:                a, b = x + dx, y + dy                if 0 <= a and a < n and 0 <= b and b < m and filling[a][b] >= 0 and filling[a][b] != i \                        and filling[a][b] not in domino_neighbours[i]:                    domino_neighbours[i].add(filling[a][b])                    degree[i] += 1        # Первым делом нужно найти такой порядок вершин, все вершины имели не больше 5 соседей среди    # предыдущих. Такой существует в силу того, что граф планарный, а найти его эффективнее всего    # по очереди находя вершину наименшей степени и удаляя её из графа, так мы получем обратный порядок    active_degrees = [set() for i in range(max(degree) + 1)]    for i, deg in enumerate(degree):        active_degrees[deg].add(i)        reversed_order = []        for step in range(len(domino_tiles)):        min_degree = min([i for i, dominoes in enumerate(active_degrees) if len(dominoes) > 0])        domino = active_degrees[min_degree].pop()                reversed_order.append(domino)        for other in domino_neighbours[domino]:            if other in active_degrees[degree[other]]:                active_degrees[degree[other]].remove(other)                degree[other] -= 1                active_degrees[degree[other]].add(other)                            # Теперь перебираем в обратном порядке и либо красим в еще не занятый цвет,    # если есть свободный из 5 цветов, иначе находим цепочку из чередующихся цветов,    # которые могут быть перекрашены. Такая найдется в силу планарности    colors = [-1 for domino in domino_tiles]    slices = [draw_filling(result)]    for domino in reversed(reversed_order):        used_colors = [colors[other] for other in domino_neighbours[domino] if colors[other] != -1]                domino_color = len(used_colors)        for i, color in enumerate(sorted(set(used_colors))):            if i != color:                domino_color = i                break             if domino_color < 5:            colors[domino] = domino_color            for x, y in domino_tiles[domino]:                result[x][y] = domino_color                            slices.append(draw_filling(result))                    continue                   # Начиная отсюда код я не тестировал, не нашел примера                c = 0        other = [other for other in domino_neighbours[domino] if colors[other] == c]        visited = set([other])        q = Queue()        q.put(other)        domino_was_reached = False        while not q.empty():            cur = q.get()            for other in domino_neighbours[cur]:                if other == domino:                    domino_was_reached = True                    break                if color[other] == c or color[other] == c + 1 and other not in visited:                    visited.add(other)                    q.put(other)                            if not domino_was_reached:            for other in visited:                color[other] = color[other] ^ 1                for x, y in domino_tiles[other]:                    result[x][y] = color[other]            color[domino] = c            for x, y in domino_tiles[domino]:                result[x][y] = c                            slices.append(draw_filling(result))            continue                    # Проделываем тоже самое для 2 и 3.        c = 2        other = [other for other in domino_neighbours[domino] if colors[other] == c]        visited = set([other])        q = Queue()        q.put(other)        domino_was_reached = False        while not q.empty():            cur = q.get()            for other in domino_neighbours[cur]:                if other == domino:                    domino_was_reached = True                    break                if color[other] == c or color[other] == c + 1 and other not in visited:                    visited.add(other)                    q.put(other)        for other in visited:            color[other] = color[other] ^ 1            for x, y in domino_tiles[other]:                result[x][y] = color[other]        color[domino] = c        for x, y in domino_tiles[domino]:            result[x][y] = c        slices.append(draw_filling(result))                        return result, slicesfilling_colored, slices =color_5(sequencial_match[-1])animate_list(slices, play=True);

def convex_hull_state(points, lower_path, upper_path):    fig = plt.figure(figsize=(6, 6))    ax = fig.add_axes([0, 0, 1, 1])        ax.get_xaxis().set_visible(False)    ax.get_yaxis().set_visible(False)    for name, spine in ax.spines.items():        spine.set_visible(False)        spine.set_visible(False)        ax.scatter([x for x, y in points], [y for x, y in points])    ax.plot([x for x, _ in lower_path], [y for _, y in lower_path], color='red')    ax.plot([x for x, _ in upper_path], [y for _, y in upper_path], color='blue')        plt.close(fig)    return figdef vector_prod(point_a, point_b):    return point_a[0] *  point_b[1] - point_a[1] * point_b[0]def convex_hull(poitns):    sorted_points = sorted(points, key=lambda x: x[1])    sorted_points = sorted(sorted_points, key=lambda x: x[0])    states = []        upper_path = [sorted_points[0]]    lower_path = [sorted_points[0]]    states.append(convex_hull_state(points, lower_path, upper_path))        for point in sorted_points[1:]:        while len(upper_path) > 1 and vector_prod(point - upper_path[-1], upper_path[-1] - upper_path[-2]) > 0:            upper_path = upper_path[:-1]            upper_path.append(point)            states.append(convex_hull_state(poitns, lower_path, upper_path))            upper_path = upper_path[:-1]        upper_path.append(point)        states.append(convex_hull_state(points, lower_path, upper_path))            for point in sorted_points[1:]:        while len(lower_path) > 1 and vector_prod(point - lower_path[-1], lower_path[-1] - lower_path[-2]) < 0:            lower_path = lower_path[:-1]            lower_path.append(point)            states.append(convex_hull_state(poitns, lower_path, upper_path))            lower_path = lower_path[:-1]        lower_path.append(point)        states.append(convex_hull_state(poitns, lower_path, upper_path))        return statespoints = [np.random.rand(2) for i in range(20)]states = convex_hull(points)animate_list(states, play=True, interval=300);

# Обертка для упрощения работы с графамиfrom graph_utils.graph import Graph, Arc, Nodedef enter_node(node):    node.SetColor('blue')    def enter_arc(node, arc):    node.SetColor('green')    arc.attributes['style'] = 'dashed'    arc.attributes['color'] = 'green'    def return_from_arc(node, arc):    arc.attributes['style'] = 'solid'    arc.attributes['color'] = 'red'    node.SetColor('blue')    def ignore_arc(arc):    arc.attributes['color'] = 'blue'    def leave_node(node):    node.SetColor('red')    def dfs(graph, node_id, visited, outlist, path):    visited.add(node_id)    path.append(node_id)    enter_node(graph.nodes[node_id])    outlist.append(graph.Visualize())    for arc in graph.nodes[node_id].arcs:        if arc.end not in visited:            enter_arc(graph.nodes[node_id], arc)            dfs(graph, arc.end, visited, outlist, path)             return_from_arc(graph.nodes[node_id], arc)            path.append(node_id)        else:            ignore_arc(arc)        outlist.append(graph.Visualize())          leave_node(graph.nodes[node_id])arcs = [    Arc(1, 3, 3),    Arc(1, 4, 7),    Arc(4, 3, 2),    Arc(4, 5, 3),    Arc(1, 5, 2),    Arc(6, 4, 2),    Arc(5, 6, 2),    Arc(6, 7, 1),    Arc(7, 2, 7),    Arc(4, 2, 2),    Arc(3, 2, 5)]# Если следующий код выдает ошибку, что ему не удается выполнить `dot`, то# скорее всего придется отдельно поставить graphviz# https://graphviz.org/download/graph = Graph(arcs)visited = set()dfs_outlist = []path = []dfs_outlist.append(graph.Visualize())dfs(graph, 1, visited, dfs_outlist, path)dfs_outlist.append(graph.Visualize())animate_list(dfs_outlist, play=True, interval=400);

def mark_labelled(node):    node.SetColor('red')    def mark_scanned(node):    node.SetColor('green')    def process_node(node):    node.SetColor('blue')    def set_previous(arc):    arc.SetColor('green')    def unset_previous(arc):    arc.SetColor('black')def scan_arc(graph, arc, l, p, mark):    if l[arc.end] > l[arc.beginning] + arc.weight:        l[arc.end] = l[arc.beginning] + arc.weight        if p[arc.end] is not None:            unset_previous(p[arc.end])        # Сохраняем arc, а не arc.beginning, чтобы было больше информации        p[arc.end] = arc        set_previous(p[arc.end])        mark[arc.end] = True        mark_labelled(graph.nodes[arc.end])def scan_node(graph, node_id, l, p, mark):    for arc in graph.nodes[node_id].arcs:        scan_arc(graph, arc, l, p, mark)    mark[node_id] = False    mark_scanned(graph.nodes[node_id])             # Это не традиционная реализация алгоритма Дейкстры, а реализация# сканирующего метода, подробности смотрите тут# http://forskning.diku.dk/PATH05/GoldbergSlides.pdfdef base_scanning_method(graph, s, choice_function):    l    = {key: float('Inf') for key in graph.nodes.keys()}    p    = {key: None for key in graph.nodes.keys()}    mark = {key: False for key in graph.nodes.keys()}        l[s] = 0    mark[s] = True    mark_labelled(graph.nodes[s])        out_lst = []        while True:        node_id = choice_function(l, mark)        if node_id is None:            break        process_node(graph.nodes[node_id])        out_lst.append(graph.Visualize(l))        scan_node(graph, node_id, l, p, mark)        out_lst.append(graph.Visualize(l))    return l, p, out_lst# Функция выбора в алгоритме Дейкстрыdef least_distance_choice(l, mark):    labelled = [node_id for node_id, value in mark.items() if value == True]    if len(labelled) == 0:        return None    return min(labelled, key=lambda x: l[x]) graph = Graph(arcs)l, p, bfs_shortest_path_lst = \    base_scanning_method(graph, 1, least_distance_choice)animate_list(bfs_shortest_path_lst, play=True, interval=400);

class TrieNode:    def __init__(self, parent, word=None):        # Хранение этого поля очень расточительно, используется исключительно        # для демонстрации ленивого подсчета суффиксных ссылок        self.parent = parent        # Здесь аналогично, это поле чаще всего избыточно        self.word = word        self.children = {}        self.suff_link = Nonedef init_trie():    trie = [TrieNode(-1)]    return triedef to_graph(trie):    arcs = []    for i, node in enumerate(trie):        for c, nextstate in node.children.items():            arcs.append(Arc(i, nextstate, c))        if node.suff_link is not None and node.suff_link != 0:            arcs.append(Arc(i,                             node.suff_link,                             attributes={"constraint" : "False", "style" : "dashed"}))                return Graph(arcs)def add_word(trie, word, steps):    _num = 0    for ch in word:        if not ch in trie[_num].children:            _n = len(trie)            trie[_num].children[ch] = _n            trie.append(TrieNode((_num, ch)))        _num = trie[_num].children[ch]        graph = to_graph(trie)        graph.nodes[_num].SetColor('red')        steps.append(graph.Visualize())    trie[_num].word = word    def make_trie(words):    steps = []    trie = init_trie()    steps.append(to_graph(trie).Visualize())    for word in words:        add_word(trie, word, steps)        steps.append(to_graph(trie).Visualize())    return trie, stepswords = [    'мама',    'мать',    'мартышка',    'мыла',    'молоко']trie, steps = make_trie(words)animate_list(steps, play=True, interval=500);

def mark_for_delete(arc):    arc.SetColor('red')    arc.SetStyle('dashed')    def mark_for_add(arc):    arc.SetColor('blue')    def clear(arc):    arc.SetColor('black')    arc.SetStyle('solid')        def find_augmenting_path(graph, node_id, visited, match, deleted):    if node_id in visited:        return False    visited.add(node_id)    for arc in graph.nodes[node_id].arcs:        if arc.end not in match or find_augmenting_path(graph, match[arc.end].beginning, visited, match, deleted):            if arc.end in match:                mark_for_delete(match[arc.end])                deleted.append(match[arc.end])            match[arc.end] = arc            mark_for_add(arc)            return True    return Falsedef kuhns_matching(graph, first_part):    states = [graph.Visualize()]    match = dict()    for node_id in first_part:        node = graph.nodes[node_id]        node.SetColor('Blue')        states.append(graph.Visualize())        deleted = []        if find_augmenting_path(graph, node_id, set(), match, deleted):            states.append(graph.Visualize())            for arc in deleted:                clear(arc)            states.append(graph.Visualize())        node.SetColor('red')    states.append(graph.Visualize())    return statesarcs = [    Arc(1, 6),    Arc(1, 7),    Arc(2, 6),    Arc(3, 7),    Arc(3, 8),    Arc(4, 8),    Arc(4, 9),    Arc(4, 10),    Arc(5, 10),    Arc(2, 8)]first_part = [1, 2, 3, 4, 5]graph = Graph(arcs)states = kuhns_matching(graph, first_part)animate_list(states, play=True, interval=400);

from animation_utils.latex import Matrixfrom IPython.display import Mathn = 5A = np.random.rand(n, n)L = np.identity(n)U = np.array(A)steps = []steps.append(Math(str(Matrix(L)) + str(Matrix(U))))for k in range(n):    x = U[k,k]    for i in range(k+1, n):        L[i,k] = U[i,k] / x        U[i,k:] -= L[i,k] * U[k,k:]    steps.append(Math(str(Matrix(L)) + str(Matrix(U))))animate_list(steps, play=True, interval=500);