Permutations_and_Combinations.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Permutations and Combinations\n",
    "\n",
    "## Permutations\n",
    "\n",
    "In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called __permuting__. The study of permutations of finite sets is a topic in the field of [combinatorics](https://en.wikipedia.org/wiki/Combinatorics). \n",
    "\n",
    "We find the number of $k$-permutations of $A$, first by determining the set of permutations and then by calculating $\\frac{|A|!}{(|A|-k)!}$. We first consider the special case of $k=|A|$, which is equivalent to finding the number of ways of ordering the elements of $A$. First we import the  **itertools** library."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![rubiks_cube](https://upload.wikimedia.org/wikipedia/commons/a/a6/Rubik%27s_cube.svg)\n",
    "\n",
    "### In the popular puzzle Rubik's cube invented in 1974 by Ernő Rubik, each turn of the puzzle faces creates a permutation of the surface colors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import itertools"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "A = {1, 2, 3}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### All permutations of A and |A!|"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Permutations of {1, 2, 3}:  \n",
      "(3, 1, 2)\n",
      "(1, 3, 2)\n",
      "(3, 2, 1)\n",
      "(2, 3, 1)\n",
      "(1, 2, 3)\n",
      "(2, 1, 3)\n",
      "Number of permutations:  6\n"
     ]
    }
   ],
   "source": [
    "# Find all permutations of A and |A!|\n",
    "permute_all = set(itertools.permutations(A))\n",
    "print(\"Permutations of %s:  \" %A)\n",
    "for i in permute_all:\n",
    "    print(i)\n",
    "print;print (\"Number of permutations: \", len(permute_all))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "# Find |A|! directly\n",
    "from math import factorial\n",
    "print(factorial(len(A)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "A = {1, 2, 3, 4}\n",
    "k = 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3-permutations of {1, 2, 3, 4}:  \n",
      "(1, 2, 3)\n",
      "(1, 2, 4)\n",
      "(1, 3, 2)\n",
      "(1, 3, 4)\n",
      "(1, 4, 2)\n",
      "(1, 4, 3)\n",
      "(2, 1, 3)\n",
      "(2, 1, 4)\n",
      "(2, 3, 1)\n",
      "(2, 3, 4)\n",
      "(2, 4, 1)\n",
      "(2, 4, 3)\n",
      "(3, 1, 2)\n",
      "(3, 1, 4)\n",
      "(3, 2, 1)\n",
      "(3, 2, 4)\n",
      "(3, 4, 1)\n",
      "(3, 4, 2)\n",
      "(4, 1, 2)\n",
      "(4, 1, 3)\n",
      "(4, 2, 1)\n",
      "(4, 2, 3)\n",
      "(4, 3, 1)\n",
      "(4, 3, 2)\n",
      "Size = 4!/(4-3)! = 24\n"
     ]
    }
   ],
   "source": [
    "# Print all the k-permutations of A\n",
    "n = len(A)\n",
    "permute_k = list(itertools.permutations(A, k))\n",
    "print(\"%i-permutations of %s:  \" %(k,A))\n",
    "for i in permute_k:\n",
    "    print(i)\n",
    "print;\n",
    "print (\"Size = {}!/({}-{})! = {}\".format(n,n,k, len(permute_k)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "24\n"
     ]
    }
   ],
   "source": [
    "# Print |A|!/(|A|-k)! directly\n",
    "print(int(factorial(len(A))/factorial(len(A)-k)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Combinations\n",
    "\n",
    "Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics, from evolutionary biology to computer science, etc.\n",
    "\n",
    "Combinatorics is well known for the breadth of the problems it tackles. Combinatorial problems arise in many areas of pure mathematics, notably in algebra, [probability theory](https://en.wikipedia.org/wiki/Probability_theory), [topology](https://en.wikipedia.org/wiki/Topology), and geometry, as well as in its many application areas. Many combinatorial questions have historically been considered in isolation, giving an _ad hoc_ solution to a problem arising in some mathematical context. In the later twentieth century, however, powerful and general theoretical methods were developed, making combinatorics into an independent branch of mathematics in its own right. One of the oldest and most accessible parts of combinatorics is [graph theory](https://en.wikipedia.org/wiki/Graph_theory), which by itself has numerous natural connections to other areas. Combinatorics is used frequently in computer science to obtain formulas and estimates in the [analysis of algorithms](https://en.wikipedia.org/wiki/Analysis_of_algorithms).\n",
    "\n",
    "We find the number of $k$-combinations of $A$, first by determining the set of combinations and then by simply calculating ${|A|}\\choose{k}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from scipy.special import binom          # to calculate the binomial coefficients |A| choose k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "A = {1, 2, 3, 4}\n",
    "k = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2-combinations of {1, 2, 3, 4}:  \n",
      "(1, 2)\n",
      "(1, 3)\n",
      "(1, 4)\n",
      "(2, 3)\n",
      "(2, 4)\n",
      "(3, 4)\n",
      "Number of combinations = 4!/(2!(4-2)!) = 6\n"
     ]
    }
   ],
   "source": [
    "# Print all the k-combinations of A\n",
    "choose_k = list(itertools.combinations(A,k))\n",
    "print(\"%i-combinations of %s:  \" %(k,A))\n",
    "for i in choose_k:\n",
    "    print(i)\n",
    "print;print(\"Number of combinations = %i!/(%i!(%i-%i)!) = %i\" %(n,k,n,k,len(choose_k)  ))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "# Print |A|!/(k!(|A|-k)!) directly\n",
    "print(int(factorial(len(A))/(factorial(k)*factorial(len(A)-k))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### If you want to concatenate characters such as letters of the English alphabet and print them as strings, you can use the _join()_ function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3-permutations of {'a', 'h', 'm', 't'}:\n",
      "ahm,aht,amh,amt,ath,atm,ham,hat,hma,hmt,hta,htm,mah,mat,mha,mht,mta,mth,tah,tam,tha,thm,tma,tmh,Size =  4!/(4-3)! =  24\n",
      "\n",
      "\n",
      "4-permutations of {'a', 'h', 'm', 't'}:\n",
      "ahmt,ahtm,amht,amth,athm,atmh,hamt,hatm,hmat,hmta,htam,htma,maht,math,mhat,mhta,mtah,mtha,tahm,tamh,tham,thma,tmah,tmha,Size =  4!/(4-4)! =  24\n"
     ]
    }
   ],
   "source": [
    "A = {'m','a','t','h'}\n",
    "k = 3\n",
    "# Print all the k-permutations of S\n",
    "n = len(A)\n",
    "permute_k = list(itertools.permutations(A, k))\n",
    "print(\"%i-permutations of %s:\" %(k,A))\n",
    "for i in range(0, len(permute_k)):\n",
    "    print(''.join(permute_k[i]),end=',')\n",
    "print;print (\"Size =  %i!/(%i-%i)! = \" %(n,n,k), len(permute_k))\n",
    "\n",
    "print(\"\\n\")\n",
    "\n",
    "n = len(A)\n",
    "k=4\n",
    "permute_k = list(itertools.permutations(A, 4))\n",
    "print(\"%i-permutations of %s:\" %(k,A))\n",
    "for i in range(0, len(permute_k)):\n",
    "    print(''.join(permute_k[i]),end=',')\n",
    "print;print (\"Size =  %i!/(%i-%i)! = \" %(n,n,k), len(permute_k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "24\n"
     ]
    }
   ],
   "source": [
    "# Print |A|!/(|A|-k)! directly\n",
    "print(int(factorial(len(A))/factorial(len(A)-k)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "A = {'a', 'b', 'c', 'd'}\n",
    "k = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2-combinations of {'a', 'd', 'b', 'c'}:\n",
      "\n",
      "ad\n",
      "ab\n",
      "ac\n",
      "db\n",
      "dc\n",
      "bc\n",
      "Size = 4!/(2!(4-2)!) =  6\n"
     ]
    }
   ],
   "source": [
    "# Print all the k-combinations of A\n",
    "choose_k = list(itertools.combinations(A,k))\n",
    "print(\"%i-combinations of %s:\\n\" %(k,A))\n",
    "for i in range(0, len(choose_k)):\n",
    "    print(''.join(choose_k[i]) )\n",
    "print;print (\"Size = %i!/(%i!(%i-%i)!) = \" %(n,k,n,k), len(choose_k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "# Print |A|!/(k!(|A|-k)!) directly\n",
    "print(int(factorial(len(A))/(factorial(k)*factorial(len(A)-k))))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.2"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "navigate_num": "#000000",
    "navigate_text": "#333333",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700",
    "sidebar_border": "#EEEEEE",
    "wrapper_background": "#FFFFFF"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "48px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "threshold": 4,
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": "block",
   "toc_window_display": false,
   "widenNotebook": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}