permutations.ipynb

permutations.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyNGR1TyMXaEgmFUqkYuucCD",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/gist/somacdivad/29265639ee26f3c9206b7c8ce5af46c8/permutations.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "oOg_Nctq_Ubi"
      },
      "outputs": [],
      "source": [
        "import itertools\n",
        "\n",
        "# Symmetric group S_n\n",
        "# NOTE: The permutations are on 0...n-1 instead of 1...n\n",
        "# This helps simplify computations later because the set aligns with 0-based indices for tuples\n",
        "S = lambda n: itertools.permutations(range(n))"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# Example: Show the elements of S_3\n",
        "list(S(3))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "WaOpwUas_qHs",
        "outputId": "6a403290-5047-421b-8eb6-da9184b52da5"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]"
            ]
          },
          "metadata": {},
          "execution_count": 34
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# This function returns an **iterator** over pairs of permutations whose product is some permutation p\n",
        "def products(p):\n",
        "    n = len(p)\n",
        "    for a, b in itertools.product(S(n), S(n)):\n",
        "        for i in range(n):\n",
        "            if b[a[i]] != p[i]:\n",
        "                break\n",
        "        else:\n",
        "            yield a, b"
      ],
      "metadata": {
        "id": "powcgaTZ_tUN"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Example of using the products() function\n",
        "\n",
        "# Helper function to generate the identity element of S_n\n",
        "id_ = lambda n: tuple(range(n))  # Ex: id_(3) = (0, 1, 2)\n",
        "\n",
        "# Show all permutations in S_3 whose product is id_(3)\n",
        "# Note that the output includes the identity element itself.\n",
        "# If you want to exclude that you could modify outer for loop in the products() function\n",
        "p = id_(3)\n",
        "list(products(p))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "2QMNkTfQBOcx",
        "outputId": "f10c9238-e7fc-45c4-81b0-f269ca4405de"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[((0, 1, 2), (0, 1, 2)),\n",
              " ((0, 2, 1), (0, 2, 1)),\n",
              " ((1, 0, 2), (1, 0, 2)),\n",
              " ((1, 2, 0), (2, 0, 1)),\n",
              " ((2, 0, 1), (1, 2, 0)),\n",
              " ((2, 1, 0), (2, 1, 0))]"
            ]
          },
          "metadata": {},
          "execution_count": 35
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# Timings for a few different values of n\n",
        "p = id_(4)\n",
        "%timeit list(products(p))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "bdGlyykBBTex",
        "outputId": "52de31b3-849d-457e-d978-19e3a9499198"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "235 µs ± 4.56 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "p = id_(5)\n",
        "%timeit list(products(p))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "3qxIQ-adCZlQ",
        "outputId": "6744ca3b-31fe-4a21-ee2a-ef5adfc48c2d"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5.51 ms ± 86.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "p = id_(6)\n",
        "%timeit list(products(p))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "GGFbFduWCduE",
        "outputId": "77f6fc0d-70c7-4ccc-ff48-ec10e61d420e"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "193 ms ± 1.46 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "p = id_(7)\n",
        "%timeit list(products(p))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "kCEzzjk1Cjve",
        "outputId": "8c4ff749-82f4-4599-bc46-c697cdf1bf8c"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "9.58 s ± 236 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# I couldn't get this to finish running on the free Google Colab 🤣\n",
        "# but that's just because %timeit tries to run it 7 different times so\n",
        "# the memory usage us 7x what just calling `list(products(p))` once would be.\n",
        "# Executing the cell without %timeit takes ~9 minutes.\n",
        "p = id_(8)\n",
        "%timeit list(products(p))"
      ],
      "metadata": {
        "id": "GDSi9JAjCpJm"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}