第四章代码.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第四章代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 算法4.1: Partition "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# author: Zeqi Zhu (sy2242117@buaa.edu.cn)\n",
    "\n",
    "def partition(arr, p, r):\n",
    "    x = arr[r]  # Choose the last element as pivot\n",
    "    i = p - 1   # Place for swapping\n",
    "    for j in range(p, r):\n",
    "        if arr[j] <= x:\n",
    "            i = i + 1\n",
    "            arr[i], arr[j] = arr[j], arr[i]  # Swap if element is less than or equal to pivot\n",
    "    arr[i + 1], arr[r] = arr[r], arr[i + 1]  # Swap the pivot element with the element at i+1\n",
    "    return i + 1  # Return the partitioning index\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 算法4.2: QuickSort "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8]\n"
     ]
    }
   ],
   "source": [
    "def quicksort(arr, p, r):\n",
    "    if p < r:\n",
    "        q = partition(arr, p, r)  # Use the partition function implemented earlier\n",
    "        quicksort(arr, p, q - 1)  # Recursively sort the left half\n",
    "        quicksort(arr, q + 1, r)  # Recursively sort the right half\n",
    "    return arr\n",
    "\n",
    "# Example usage\n",
    "arr = [2, 8, 7, 1, 3, 5, 6, 4]\n",
    "print(quicksort(arr, 0, len(arr) - 1))  # Output: [1, 2, 3, 4, 5, 6, 7, 8]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 算法4.3: Randomized-Partition "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def randomized_partition(arr, p, r):\n",
    "    s = random.randint(p, r)  # Randomly select a pivot index between p and r\n",
    "    arr[s], arr[r] = arr[r], arr[s]  # Swap the pivot element with the last element\n",
    "    q = partition(arr, p, r)  # Use the previously implemented partition function\n",
    "    return q\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 算法4.4: Selection "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "def selection(arr, p, r, k):\n",
    "    if p == r:\n",
    "        return arr[p]\n",
    "    \n",
    "    q = partition(arr, p, r)  # Use the partition function implemented earlier\n",
    "    i = q - p + 1  # The rank of the pivot element\n",
    "\n",
    "    if k == i:  # The pivot element is the answer\n",
    "        return arr[q]\n",
    "    elif k < i:  # If the desired index is less than the rank of the pivot\n",
    "        return selection(arr, p, q - 1, k)\n",
    "    else:  # If the desired index is more than the rank of the pivot\n",
    "        return selection(arr, q + 1, r, k - i)\n",
    "\n",
    "# Example usage\n",
    "arr = [6, 10, 13, 5, 8, 3, 2, 11, 7]\n",
    "print(selection(arr, 0, len(arr) - 1, 3))  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 算法4.5: RandomSelection "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "def random_selection(arr, p, r, k):\n",
    "    if p == r:\n",
    "        return arr[p]\n",
    "\n",
    "    q = randomized_partition(arr, p, r)  # Use the randomized_partition function implemented earlier\n",
    "    i = q - p + 1  # The rank of the pivot element\n",
    "\n",
    "    if k == i:  # The pivot element is the answer\n",
    "        return arr[q]\n",
    "    elif k < i:  # If the desired index is less than the rank of the pivot\n",
    "        return random_selection(arr, p, q - 1, k)\n",
    "    else:  # If the desired index is more than the rank of the pivot\n",
    "        return random_selection(arr, q + 1, r, k - i)\n",
    "    \n",
    "# Example usage\n",
    "arr = [6, 10, 13, 5, 8, 3, 2, 11, 7]\n",
    "print(random_selection(arr, 0, len(arr) - 1, 3)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 算法4.6: PolyMulti "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[6, 5, 1]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Implementing the PolyMulti function for polynomial multiplication using the pseudocode in the image\n",
    "\n",
    "def poly_multi(A, B):\n",
    "    if len(A) == 0 or len(B) == 0:\n",
    "        return [0]\n",
    "    \n",
    "    # Calculate the size of the numbers\n",
    "    n = max(len(A), len(B))\n",
    "    m = n // 2\n",
    "    \n",
    "    # Base case: if the polynomial has only one coefficient\n",
    "    if n == 1:\n",
    "        return [A[0] * B[0]]\n",
    "    \n",
    "    # Split the polynomials into two halves\n",
    "    A0 = A[:m]\n",
    "    A1 = A[m:]\n",
    "    B0 = B[:m]\n",
    "    B1 = B[m:]\n",
    "    \n",
    "    # Making sure both halves have the same size by filling with 0s if necessary\n",
    "    A0 += [0] * (m - len(A0))\n",
    "    A1 += [0] * (m - len(A1))\n",
    "    B0 += [0] * (m - len(B0))\n",
    "    B1 += [0] * (m - len(B1))\n",
    "    \n",
    "    U = poly_multi(A0, B0)\n",
    "    V = poly_multi(A0, B1)\n",
    "    W = poly_multi(A1, B0)\n",
    "    Z = poly_multi(A1, B1)\n",
    "\n",
    "\n",
    "    # Constructing the result polynomial\n",
    "    result = [0] * (2 * n - 1)\n",
    "    for i in range(n - 1):\n",
    "        result[i] += U[i]\n",
    "        result[i + n] += Z[i]\n",
    "        result[i + m] += V[i] + W[i]\n",
    "    \n",
    "    return result\n",
    "\n",
    "# Test the PolyMulti function with two polynomials represented as coefficients list\n",
    "# For example, let's multiply (2 + x)(3 + x) which should return [6, 5, 1]\n",
    "# Representing the polynomials as coefficients list, where the index is the power of x:\n",
    "# (2 + x) -> [2, 1]\n",
    "# (3 + x) -> [3, 1]\n",
    "poly1 = [2, 1]\n",
    "poly2 = [3, 1]\n",
    "\n",
    "poly_multi_result = poly_multi(poly1, poly2)\n",
    "poly_multi_result\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 算法4.7:PolyMulti-OPT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 10, 8]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def poly_multi_opt(A, B):\n",
    "    if len(A) == 0 or len(B) == 0:\n",
    "        return [0]\n",
    "    \n",
    "    # Calculate the size of the numbers\n",
    "    n = max(len(A), len(B))\n",
    "    m = n // 2\n",
    "    \n",
    "    # Base case: if the polynomial has only one coefficient\n",
    "    if n == 1:\n",
    "        return [A[0] * B[0]]\n",
    "    \n",
    "    # Split the polynomials into two halves\n",
    "    A0 = A[:m]\n",
    "    A1 = A[m:]\n",
    "    B0 = B[:m]\n",
    "    B1 = B[m:]\n",
    "    \n",
    "    # Making sure both halves have the same size by filling with 0s if necessary\n",
    "    A0 += [0] * (m - len(A0))\n",
    "    A1 += [0] * (m - len(A1))\n",
    "    B0 += [0] * (m - len(B0))\n",
    "    B1 += [0] * (m - len(B1))\n",
    "    \n",
    "    # Recursive calls\n",
    "    U = poly_multi_opt(A0, B0)\n",
    "    Z = poly_multi_opt(A1, B1)\n",
    "    Y = poly_multi_opt([a0 + a1 for a0, a1 in zip(A0, A1)], [b0 + b1 for b0, b1 in zip(B0, B1)])\n",
    "    \n",
    "    # Constructing the result polynomial\n",
    "    result = [0] * (2 * n - 1)\n",
    "    for i in range(n - 1):\n",
    "        result[i] += U[i]\n",
    "        result[i + n] += Z[i]\n",
    "        result[i + m] += Y[i] - U[i] - Z[i]\n",
    "    \n",
    "    return result\n",
    "\n",
    "# Test the implementation with an example\n",
    "A = [1, 2] # Represents the polynomial 1 + 2x\n",
    "B = [3, 4] # Represents the polynomial 3 + 4x\n",
    "\n",
    "# The expected result is [3, 10, 8] which represents the polynomial 3 + 10x + 8x^2\n",
    "poly_multi_opt(A, B)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 算法4.8: ClosestPair "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((3, 4), (4, 4), 1.0)"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def closest_pair(points):\n",
    "    def dist(p1, p2):\n",
    "        return ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5\n",
    "\n",
    "    def brute_force(pts):\n",
    "        min_dist = dist(pts[0], pts[1])\n",
    "        min_pair = (pts[0], pts[1])\n",
    "        for i in range(len(pts) - 1):\n",
    "            for j in range(i + 1, len(pts)):\n",
    "                if dist(pts[i], pts[j]) < min_dist:\n",
    "                    min_dist = dist(pts[i], pts[j])\n",
    "                    min_pair = (pts[i], pts[j])\n",
    "        return min_pair[0], min_pair[1], min_dist\n",
    "\n",
    "    def recursive_closest_pair(pts):\n",
    "        if len(pts) <= 3:\n",
    "            return brute_force(pts)\n",
    "\n",
    "        mid = len(pts) // 2\n",
    "        left_pts = pts[:mid]\n",
    "        right_pts = pts[mid:]\n",
    "\n",
    "        (p1, q1, dist1) = recursive_closest_pair(left_pts)\n",
    "        (p2, q2, dist2) = recursive_closest_pair(right_pts)\n",
    "\n",
    "        d = min(dist1, dist2)\n",
    "        (p, q) = (p1, q1) if dist1 < dist2 else (p2, q2)\n",
    "\n",
    "        # Construct a strip to check points on different sides of the partition.\n",
    "        strip = [p for p in pts if abs(p[0] - pts[mid][0]) < d]\n",
    "\n",
    "        strip.sort(key=lambda point: point[1])  # Sort strip according to y coordinate\n",
    "\n",
    "        # Find the closest points in strip. (In strip, not the whole set)\n",
    "        for i in range(len(strip)):\n",
    "            for j in range(i + 1, len(strip)):\n",
    "                if strip[j][1] - strip[i][1] < d:\n",
    "                    dist_strip = dist(strip[i], strip[j])\n",
    "                    if dist_strip < d:\n",
    "                        d = dist_strip\n",
    "                        p, q = strip[i], strip[j]\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        return p, q, d\n",
    "\n",
    "    # Sort the points by their x-coordinate\n",
    "    points = sorted(points, key=lambda x: x[0])\n",
    "    point1, point2, minimum_distance = recursive_closest_pair(points)\n",
    "    return point1, point2, minimum_distance\n",
    "\n",
    "# This function can now be used with a set of points to find the closest pair.\n",
    "# Example usage with dummy points:\n",
    "dummy_points = [(0, 0), (1, 1), (2, 2), (4, 4), (5, 5), (3, 4)]\n",
    "\n",
    "# Run the function with the dummy points\n",
    "closest_pair(dummy_points)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "py38_torch",
   "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.8.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}