Algorithms.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithms\n",
    "\n",
    "This notebook represents algorithms from different sources.\n",
    "\n",
    "Kashirin Aleksandr\n",
    "\n",
    "05/2022\n",
    "\n",
    "### 1. Binary search - $O(log_2n)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(lst:list, item:int) -> int:\n",
    "    \"\"\"Function performs binary search for the Python sorted integer list. \n",
    "    Algorithm complexity: O(log2(n)).\n",
    "\n",
    "    Args:\n",
    "        lst (list): Sorted list\n",
    "        item (int): Item to be searched \n",
    "\n",
    "    Returns:\n",
    "        ind (int): Index of the item\n",
    "        count (int): Counter of the required operations\n",
    "    \"\"\"\n",
    "\n",
    "    # Set low and high bounds\n",
    "    low = 0\n",
    "    high = len(lst)-1\n",
    "    # Set operation counter\n",
    "    count = 0\n",
    "\n",
    "    while low <= high:\n",
    "        mid = (low + high) // 2  # Set mid point\n",
    "        guess = lst[mid]\n",
    "        if guess == item:       # If guess is correct\n",
    "            return mid, count\n",
    "        if guess > item:        # If guess is higher\n",
    "            high = mid - 1\n",
    "        else:                   # If guess is lower\n",
    "            low = mid + 1\n",
    "        count += 1\n",
    "    return None\n",
    "\n",
    "# Example\n",
    "my_list = [x for x in range(200) if x % 2 == 0]\n",
    "ind, count = binary_search(my_list, 70)\n",
    "print('Answer:', ind, ', Operations required:', count)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Simple search - $O(n)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def simple_search(lst:list, item:int) -> int:\n",
    "    \"\"\"Function performs simple search for the Python unsorted integer list. \n",
    "    Algorithm complexity: O(n).\n",
    "\n",
    "    Args:\n",
    "        lst (list): Unsorted list\n",
    "        item (int): Item to be searched\n",
    "\n",
    "    Returns:\n",
    "        ind (int): Index of the item\n",
    "        count (int): Counter of the required operations\n",
    "    \"\"\"\n",
    "    count = 0\n",
    "    for i in range(len(lst)):\n",
    "        count += 1\n",
    "        if lst[i] == item:\n",
    "            return i, count\n",
    "            \n",
    "# Example\n",
    "ind, count = simple_search(my_list, 70)\n",
    "print('Answer:', ind, ', Operations required:', count)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Selection sort - $O(n^2)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_smallest(lst:list) -> int:\n",
    "    \"\"\"Function search for the index of the smallest element.\n",
    "    Algorithm complexity: O(n).\n",
    "\n",
    "    Args:\n",
    "        lst (list): Unsorted list\n",
    "\n",
    "    Returns:\n",
    "        smallest_index (int): Index of the smallest element\n",
    "    \"\"\"\n",
    "    smallest = lst[0]\n",
    "    smallest_index = 0\n",
    "    for i in range(len(lst)):\n",
    "        if lst[i] < smallest:\n",
    "            smallest = lst[i]\n",
    "            smallest_index = i\n",
    "    return smallest_index\n",
    "\n",
    "def selection_sort(lst:list) -> list:\n",
    "    \"\"\"Function performs selection sorting\n",
    "    Algorithm complexity: O(n^2).\n",
    "\n",
    "    Args:\n",
    "        lst (list): Unsorted list\n",
    "\n",
    "    Returns:\n",
    "        sorted_list (list): Sorted list\n",
    "    \"\"\"\n",
    "    lst_copy = lst.copy()\n",
    "    new_lst = []\n",
    "    for i in range(len(lst_copy)):\n",
    "        smallest_index = find_smallest(lst_copy)\n",
    "        new_lst.append(lst_copy[smallest_index])\n",
    "        lst_copy.pop(smallest_index)\n",
    "    return new_lst\n",
    "    \n",
    "# Example\n",
    "import numpy as np\n",
    "unsorted_list = [np.random.randint(10) for x in range(10)]\n",
    "print(\"Unsorted list:\", unsorted_list)\n",
    "sorted_list = selection_sort(unsorted_list)\n",
    "print(\"  Sorted list:\", sorted_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. Quick sort - $O(n \\cdot log_2 n)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quick_sort(lst:list) -> list:\n",
    "    \"\"\"Function performs quick sort for the Python list.\n",
    "    Average algorithm complexity: O(n * log2(n)).\n",
    "    Worst algorithm complexity: O(n^2).\n",
    "\n",
    "    Args:\n",
    "        lst (list): Unsorted list\n",
    "\n",
    "    Returns:\n",
    "        sorted_list (list): Sorted list\n",
    "    \"\"\"\n",
    "    # Basic case\n",
    "    if len(lst) <= 1:\n",
    "        return lst\n",
    "    else:\n",
    "    # Recursive case\n",
    "        pivot = lst[0] # Choose pivot point\n",
    "        less = [i for i in lst[1:] if i <= pivot]\n",
    "        greater = [i for i in lst[1:] if i > pivot]\n",
    "        return quick_sort(less) + [pivot] + quick_sort(greater)\n",
    "\n",
    "print(\"Unsorted list\", unsorted_list)\n",
    "sorted_list = quick_sort(unsorted_list)\n",
    "print(\"  Sorted list\", sorted_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5. Merge sort - $O(n \\cdot log_2n)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(left:list, right:list) -> list:\n",
    "    \"\"\"Merging procedure\n",
    "    Algorithm complexity: O(n).\n",
    "\n",
    "    Args:\n",
    "        left (list): left array side\n",
    "        right (list): right array side\n",
    "\n",
    "    Returns:\n",
    "        result (list): Resulted merged array\n",
    "    \"\"\"\n",
    "    result = list()\n",
    "    i = 0\n",
    "    j = 0\n",
    "    while (i < len(left)) and (j < len(right)):\n",
    "        if (left[i] < right[j]):\n",
    "            result.append(left[i])\n",
    "            i += 1\n",
    "        else:\n",
    "            result.append(right[j])\n",
    "            j += 1\n",
    "    # Append the rest of the arrays\n",
    "    for I in range(i, len(left)):\n",
    "        result.append(left[I])\n",
    "    for J in range(j, len(right)):\n",
    "        result.append(right[J])    \n",
    "    return result\n",
    "\n",
    "def merge_sort(lst:list) -> list:\n",
    "    \"\"\"Function performs merge sorting algorithm.\n",
    "    Algorithm complexity: O(n * log2(n)).\n",
    "\n",
    "    Args:\n",
    "        lst (list): Unsorted list\n",
    "\n",
    "    Returns:\n",
    "        result (list): Sorted list\n",
    "    \"\"\"\n",
    "    # Basic case\n",
    "    if len(lst) < 2:\n",
    "        return lst\n",
    "    # Recursive case\n",
    "    else:\n",
    "        mid = len(lst) // 2 # mid = 2\n",
    "        left = merge_sort(lst[:mid]) \n",
    "        right = merge_sort(lst[mid:])\n",
    "        return merge(left, right)\n",
    "       # return(merge(lst[:mid], lst[mid:]))\n",
    "\n",
    "print(\"Unsorted list\", unsorted_list)\n",
    "sorted_list = merge_sort(unsorted_list) # 0, 4, 3, 2\n",
    "print(\"  Sorted list\", sorted_list)  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6. Breadth First Search (BFS) - $O(Vertices+Edges)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def backtrace(parent:list, start:str, finish:str) -> list:\n",
    "    \"\"\"Additional function to recover a path from start to finish\n",
    "\n",
    "    Args:\n",
    "        parent (str): List of parent objects\n",
    "        start (str):  Starting point\n",
    "        finish (str): Finishing point\n",
    "    \"\"\"\n",
    "    path = [finish]\n",
    "    while path[-1] != start:\n",
    "        path.append(parent[path[-1]])\n",
    "    path.reverse()\n",
    "    return path\n",
    "\n",
    "def bfs_search(graph:dict, start:str, end:str) -> list:\n",
    "    \"\"\"Breadth First Search - an unweighted unidirectional graph path searching algorithm.\n",
    "    Algorithm complexity for searching: O(Vertices + Edges)\n",
    "\n",
    "    Args:\n",
    "        graph (dict): Graph structure to look in\n",
    "        start (str):  Starting point\n",
    "        end (str): Finishing point\n",
    "\n",
    "    Returns:\n",
    "        path (list): Found path\n",
    "    \"\"\"\n",
    "    # Step 1. Create a dictionary of parents\n",
    "    parent = {}\n",
    "    # Step 2. Create a queue of nodes\n",
    "    queue = []\n",
    "    queue.append(start)\n",
    "\n",
    "    # Step 3. While queue is not empty\n",
    "    while queue:\n",
    "        node = queue.pop(0)                         # Get the first element\n",
    "        if node == end:                             # If end node was reached\n",
    "            return backtrace(parent, start, end)    # Get the path to the end node\n",
    "        for child in graph.get(node, []):           # For each child in the list\n",
    "            if node not in queue :                  # If this child is not in the queue\n",
    "                parent[child] = node                # Record the parent of this child in the dictionary\n",
    "                queue.append(child)                 # Append child in the queue\n",
    "\n",
    "# Creating a graph\n",
    "graph = {}\n",
    "graph['alex'] = ['alice', 'bob', 'claire']\n",
    "graph['bob'] =  ['anuj', 'peggy']\n",
    "graph['alice'] = ['peggy']\n",
    "graph['claire'] = ['thom', 'johny']\n",
    "graph['anuj'] = []\n",
    "graph['peggy'] = []\n",
    "graph['thom'] = []\n",
    "graph['johny'] = []\n",
    "\n",
    "path = bfs_search(graph, 'alex', 'johny')\n",
    "print('Path to the end node:', end=' ')\n",
    "print(*path, sep=', ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7. Djkstra algorithm "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "a = [np.random.randint(32) for x in range(32)]\n",
    "max = a[0]\n",
    "before_max = 0\n",
    "for i in range(len(a)):\n",
    "    if a[i] > max:\n",
    "        before_max = max\n",
    "        max = a[i]\n",
    "    if (a[i] > before_max) and (a[i]) < max:\n",
    "        before_max = a[i]\n",
    "print(a)\n",
    "print(max, before_max)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8. Generate permutations of elements"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def permutations(iterable) -> list:\n",
    "    \"\"\"Function returns list of all generated permutations \n",
    "\n",
    "    Args:\n",
    "        iterable: collection or string\n",
    "\n",
    "    Returns:\n",
    "        list: list of generated permutations\n",
    "    \"\"\"\n",
    "    if len(iterable) == 1:\n",
    "        yield (iterable[0], )\n",
    "    else:\n",
    "        for perm in permutations(iterable[1:]):\n",
    "            for i in range(len(iterable)):\n",
    "                yield perm[:i] + (iterable[0], ) + perm[i:]\n",
    "\n",
    "def unique_permutations(iterable) -> list:\n",
    "    \"\"\"Function returns unique set of permutations \n",
    "\n",
    "    Args:\n",
    "        iterable: collection or string\n",
    "\n",
    "    Returns:\n",
    "        list: list of unique permutations\n",
    "    \"\"\"\n",
    "    return list(set(permutations(iterable)))\n",
    "\n",
    "\n",
    "s = 'ab'\n",
    "print([''.join(x) for x in unique_permutations(s)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9. Heap Algorithm\n",
    "\n",
    "The algorithm is used to generate permutations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['ab', 'ba']\n"
     ]
    }
   ],
   "source": [
    "\n",
    "s = [x for x in 'ab']\n",
    "res = []\n",
    "def generate_permutations(iterable: list, k: int, my_res) -> list:\n",
    "    if k == 1:\n",
    "        #print(iterable)\n",
    "        seq = \"\".join(iterable)\n",
    "        my_res.append(seq)\n",
    "        return res\n",
    "    else:\n",
    "        for i in range(k):\n",
    "            generate_permutations(iterable, k - 1, my_res)\n",
    "            if k % 2 == 0:\n",
    "                iterable[i], iterable[k-1] = iterable[k-1], iterable[i]\n",
    "            else:\n",
    "                iterable[0], iterable[k-1] = iterable[k-1], iterable[0]\n",
    "    return res\n",
    "\n",
    "seq = generate_permutations(s, len(s), res)\n",
    "\n",
    "print(seq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "s1 = \"\".join(sorted(s1))\n",
    "s2 = \"\".join(sorted(s2))\n",
    "if s1 in s2:\n",
    "    print(True)\n",
    "else:\n",
    "    print(False)"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "cf92aa13fedf815d5c8dd192b8d835913fde3e8bc926b2a0ad6cc74ef2ba3ca2"
  },
  "kernelspec": {
   "display_name": "Python 3.9.2 64-bit",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.2"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}