{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sage Tutorial for Permutation Groups\n",
    "\n",
    "You can use sage for a lot of group theory tests. The following should give you an idea of how things work in Sage. \n",
    "\n",
    "Sage has a *lot* of built-in groups that you can call. The following are a few examples. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "S4 = SymmetricGroup(4) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "D4 = DihedralGroup(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These are a few examples of groups. There is a whole lot of other ['named groups'](https://doc.sagemath.org/html/en/reference/groups/sage/groups/groups_catalog.html) that Sage has; you can look up the manual for it. \n",
    "\n",
    "Even if you find a new group, and you want to understand it more, you can ask for it to print the multiplication table:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "D4.cayley_table()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or just list the elements:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "D4.list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or even show the Cayley graph of it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "show(D4.cayley_graph())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Whenever you are unsure of what a specific command does, you can always ask for help"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "D4.cayley_graph?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Working with group elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can use the disjoint cycle notation to refer to a specific element of the group. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rho = S4([(1,2),(3,4)])\n",
    "pi = S4([(1,4),(2,3)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tau = rho * pi * rho.inverse()\n",
    "tau"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can also make membership queries (and a LOT more)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tau in D4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can also specify permutations as a single array (where the i-th element represents the image of i under this permutation)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sigma = S4([4,3,2,1])\n",
    "sigma"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Building a group "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us consider the rotations of the cube:\n",
    "\n",
    "![](https://i.stack.imgur.com/aHMgv.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "S8 = SymmetricGroup(8)\n",
    "rot_R = S8([(1,8,6,7),(4,5,2,3)])\n",
    "rot_U = S8([(5,8,1,4),(2,6,7,3)])\n",
    "rot_F = S8([(4,1,7,3),(5,8,6,2)])\n",
    "G = PermutationGroup([rot_R, rot_U, rot_F])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.order()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hmm... wonder what this group is..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.is_isomorphic(S4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Rubik's cube group (3x3x3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sage has a built-in named group for the 3x3x3 Rubik's cube."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "R3 = CubeGroup()\n",
    "R3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "R3.display2d(\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# What the cube looks like after a move sequence\n",
    "R3.display2d(\"R D R-1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(R3.orbit(2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "R3.stabilizer(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(R3.orbit(1)) * R3.stabilizer(1).order() == R3.order()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, if you are interested more in the visualisation of moves rather than the group directly, there is a related class called `RubiksCube`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "C = RubiksCube(\"R D R-1\")\n",
    "C.plot3d()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Building the nxnxn Rubik's cube group"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As a concrete example, we can try to build the general nxnxn Rubik's cube group. However, in order to build that, we need a way to label the stickers to make it easier to talk about precisely how the various moves work."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Convention for sticker names"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A natural way is to just think of each \"piece\" of the cube specified by the slice numbers in each direction. \n",
    "\n",
    " - x-slices: Start in L, and end at R\n",
    " - y-slices: Start at D, and end at U\n",
    " - z-slices: Start at F, and end at B\n",
    "\n",
    "Hence, for example, the (0,0,0) piece refers to the LDF corner. However, this alone isn't enough as we also need the face it belongs to. Well, it is enough to just specify the direction of the face as the face is determined by the slice number in that direction. We will therefore specify stickers using the notation:\n",
    "\n",
    "> (face_direction, x-slice-index, y-slice-index, z-slice-index)\n",
    "\n",
    "Thus, in general for an $n \\times n \\times n$ cube, there are $3n^2 \\cdot 2 = 6n^2$ stickers overall (once you fix a direction, the slice index in that direction can only be 0 or (n-1))."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"sticker_notation.jpg\" alt=\"Sticker notation\" width=\"500px\"/>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_layers = 3\n",
    "stickers = [\n",
    "    (face_direction, x_idx, y_idx, z_idx) \n",
    "        for face_direction in range(3)   # 0 => L/R, 1 => D/U, 2 => F/B\n",
    "        for x_idx in range(num_layers) \n",
    "        for y_idx in range(num_layers)\n",
    "        for z_idx in range(num_layers)\n",
    "        if [x_idx, y_idx, z_idx][face_direction] in [0, num_layers - 1]   \n",
    "            # eg. If we are staring at L/R, then x-cord must be 0 or n-1\n",
    "]\n",
    "SymStickers = SymmetricGroup(len(stickers))\n",
    "SymStickers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can specify what \"moves\" are. Once again, we can specify the standard moves by mentioning the direction and the slice index. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rotate_cube(direction, slice_idx, stickers, num_layers):\n",
    "    '''\n",
    "    Returns an array of permuted sticker indices (an array that is 1,...,len(stickers) permuted)\n",
    "    '''\n",
    "    output = []\n",
    "\n",
    "    for sticker in stickers:\n",
    "        face_dir, x_idx, y_idx, z_idx = sticker\n",
    "        indices = [x_idx, y_idx, z_idx]\n",
    "        \n",
    "        if slice_idx != indices[direction]:\n",
    "            # Then this piece doesn't move at all\n",
    "            new_sticker = sticker\n",
    "        else:\n",
    "            if face_dir == direction:\n",
    "                new_direction = direction\n",
    "            else:\n",
    "                # The new direction is the 'other' direction\n",
    "                new_direction = [d for d in [0,1,2] if d != face_dir and d!=direction][0]\n",
    "            \n",
    "            new_indices = [0,0,0]\n",
    "            new_indices[direction] = indices[direction]\n",
    "            new_indices[(direction + 1) % 3] = indices[(direction + 2) % 3]\n",
    "            new_indices[(direction + 2) % 3] = num_layers - 1 - indices[(direction + 1) % 3]\n",
    "\n",
    "            new_sticker = (new_direction, new_indices[0], new_indices[1], new_indices[2])\n",
    "        \n",
    "        new_sticker_index = stickers.index(new_sticker) + 1\n",
    "        output.append(new_sticker_index)\n",
    "    return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "generators = [\n",
    "                  SymStickers(rotate_cube(direction, slice_idx, stickers, num_layers))\n",
    "                      for direction in [0,1,2]\n",
    "                      for slice_idx in range(num_layers)\n",
    "             ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "R = PermutationGroup(generators)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "R.order()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "CubeGroup().order()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "R.order() / CubeGroup().order()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Can you see where the factor of 24 is from?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "CubeGroup().display2d('')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ah! We happen to be moving our centres as well! Let's fix that"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "generators = [\n",
    "                  SymStickers(rotate_cube(direction, slice_idx, stickers, num_layers))\n",
    "                      for direction in [0,1,2]\n",
    "                      for slice_idx in range(num_layers) if slice_idx != 1\n",
    "             ]\n",
    "R = PermutationGroup(generators)\n",
    "R.order() == CubeGroup().order()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Some general tutorials online"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You have a [pretty good tutorial here](http://doc.sagemath.org/html/en/thematic_tutorials/group_theory.html#permutation-groups).\n",
    "Play around with sage to get a better hang of things. "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.4",
   "language": "sage",
   "name": "sagemath-9.4"
  },
  "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}