permutations1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Permutações\n",
    "\n",
    "Vamos começar estudando o conjunto das bijeções de um conjunto finito. Mais precisamente vamos tomar o conjunto finito $ E_n = \\{1,2,\\dots,n\\} \\subset \\mathbb{N}$. Consideremos agora o conjunto de todas as funções bijetoras\n",
    "$ \\sigma : E_n \\to E_n$, ou seja $\\mathbb{S}_n=\\{\\sigma: E_n \\to E_n: (\\forall k \\in E_n \\implies \\exists l \\sigma(l)=k) \\wedge (\\sigma(r)=\\sigma(s) \\implies r=s)\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Notação de Cauchy ###\n",
    "\n",
    "Uma forma de dar a função $\\sigma$ pode ser:\n",
    "\n",
    "\n",
    "$$ \\sigma = \\left(\\begin{array}{cccc}\n",
    "1 & 2& \\cdots & n \\\\ \\sigma(1) & \\sigma(2) & \\cdots & \\sigma(n)\\end{array} \\right)$$\n",
    "que é chamada notação de Cauchy.\n",
    "\n",
    "Por exemplo $$\\sigma = \\left(\\begin{array}{ccccc}\n",
    "1 & 2& 3 & 4 & 5 \\\\ 3 & 2 & 1 & 5 & 4\\end{array} \\right)$$\n",
    "representa a função tal que $\\sigma(1)=3,$ $\\sigma(2)=2$ etc. Como é a representação da inversa desta função?\n",
    "\n",
    "Se convecionamos que na primeira linha teremos sempre os elementos ordenados, então a notação pode ser resumida \n",
    "$$ \\sigma = \\left[\\begin{array}{cccc}\n",
    "3 & 2& 1 & 5 & 4 \\end{array} \\right]$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 2, 3, 4, 5)\n",
      "(1, 2, 3, 5, 4)\n",
      "(1, 2, 4, 3, 5)\n",
      "(1, 2, 4, 5, 3)\n",
      "(1, 2, 5, 3, 4)\n",
      "(1, 2, 5, 4, 3)\n",
      "(1, 3, 2, 4, 5)\n",
      "(1, 3, 2, 5, 4)\n",
      "(1, 3, 4, 2, 5)\n",
      "(1, 3, 4, 5, 2)\n",
      "(1, 3, 5, 2, 4)\n",
      "(1, 3, 5, 4, 2)\n",
      "(1, 4, 2, 3, 5)\n",
      "(1, 4, 2, 5, 3)\n",
      "(1, 4, 3, 2, 5)\n",
      "(1, 4, 3, 5, 2)\n",
      "(1, 4, 5, 2, 3)\n",
      "(1, 4, 5, 3, 2)\n",
      "(1, 5, 2, 3, 4)\n",
      "(1, 5, 2, 4, 3)\n",
      "(1, 5, 3, 2, 4)\n",
      "(1, 5, 3, 4, 2)\n",
      "(1, 5, 4, 2, 3)\n",
      "(1, 5, 4, 3, 2)\n",
      "(2, 1, 3, 4, 5)\n",
      "(2, 1, 3, 5, 4)\n",
      "(2, 1, 4, 3, 5)\n",
      "(2, 1, 4, 5, 3)\n",
      "(2, 1, 5, 3, 4)\n",
      "(2, 1, 5, 4, 3)\n",
      "(2, 3, 1, 4, 5)\n",
      "(2, 3, 1, 5, 4)\n",
      "(2, 3, 4, 1, 5)\n",
      "(2, 3, 4, 5, 1)\n",
      "(2, 3, 5, 1, 4)\n",
      "(2, 3, 5, 4, 1)\n",
      "(2, 4, 1, 3, 5)\n",
      "(2, 4, 1, 5, 3)\n",
      "(2, 4, 3, 1, 5)\n",
      "(2, 4, 3, 5, 1)\n",
      "(2, 4, 5, 1, 3)\n",
      "(2, 4, 5, 3, 1)\n",
      "(2, 5, 1, 3, 4)\n",
      "(2, 5, 1, 4, 3)\n",
      "(2, 5, 3, 1, 4)\n",
      "(2, 5, 3, 4, 1)\n",
      "(2, 5, 4, 1, 3)\n",
      "(2, 5, 4, 3, 1)\n",
      "(3, 1, 2, 4, 5)\n",
      "(3, 1, 2, 5, 4)\n",
      "(3, 1, 4, 2, 5)\n",
      "(3, 1, 4, 5, 2)\n",
      "(3, 1, 5, 2, 4)\n",
      "(3, 1, 5, 4, 2)\n",
      "(3, 2, 1, 4, 5)\n",
      "(3, 2, 1, 5, 4)\n",
      "(3, 2, 4, 1, 5)\n",
      "(3, 2, 4, 5, 1)\n",
      "(3, 2, 5, 1, 4)\n",
      "(3, 2, 5, 4, 1)\n",
      "(3, 4, 1, 2, 5)\n",
      "(3, 4, 1, 5, 2)\n",
      "(3, 4, 2, 1, 5)\n",
      "(3, 4, 2, 5, 1)\n",
      "(3, 4, 5, 1, 2)\n",
      "(3, 4, 5, 2, 1)\n",
      "(3, 5, 1, 2, 4)\n",
      "(3, 5, 1, 4, 2)\n",
      "(3, 5, 2, 1, 4)\n",
      "(3, 5, 2, 4, 1)\n",
      "(3, 5, 4, 1, 2)\n",
      "(3, 5, 4, 2, 1)\n",
      "(4, 1, 2, 3, 5)\n",
      "(4, 1, 2, 5, 3)\n",
      "(4, 1, 3, 2, 5)\n",
      "(4, 1, 3, 5, 2)\n",
      "(4, 1, 5, 2, 3)\n",
      "(4, 1, 5, 3, 2)\n",
      "(4, 2, 1, 3, 5)\n",
      "(4, 2, 1, 5, 3)\n",
      "(4, 2, 3, 1, 5)\n",
      "(4, 2, 3, 5, 1)\n",
      "(4, 2, 5, 1, 3)\n",
      "(4, 2, 5, 3, 1)\n",
      "(4, 3, 1, 2, 5)\n",
      "(4, 3, 1, 5, 2)\n",
      "(4, 3, 2, 1, 5)\n",
      "(4, 3, 2, 5, 1)\n",
      "(4, 3, 5, 1, 2)\n",
      "(4, 3, 5, 2, 1)\n",
      "(4, 5, 1, 2, 3)\n",
      "(4, 5, 1, 3, 2)\n",
      "(4, 5, 2, 1, 3)\n",
      "(4, 5, 2, 3, 1)\n",
      "(4, 5, 3, 1, 2)\n",
      "(4, 5, 3, 2, 1)\n",
      "(5, 1, 2, 3, 4)\n",
      "(5, 1, 2, 4, 3)\n",
      "(5, 1, 3, 2, 4)\n",
      "(5, 1, 3, 4, 2)\n",
      "(5, 1, 4, 2, 3)\n",
      "(5, 1, 4, 3, 2)\n",
      "(5, 2, 1, 3, 4)\n",
      "(5, 2, 1, 4, 3)\n",
      "(5, 2, 3, 1, 4)\n",
      "(5, 2, 3, 4, 1)\n",
      "(5, 2, 4, 1, 3)\n",
      "(5, 2, 4, 3, 1)\n",
      "(5, 3, 1, 2, 4)\n",
      "(5, 3, 1, 4, 2)\n",
      "(5, 3, 2, 1, 4)\n",
      "(5, 3, 2, 4, 1)\n",
      "(5, 3, 4, 1, 2)\n",
      "(5, 3, 4, 2, 1)\n",
      "(5, 4, 1, 2, 3)\n",
      "(5, 4, 1, 3, 2)\n",
      "(5, 4, 2, 1, 3)\n",
      "(5, 4, 2, 3, 1)\n",
      "(5, 4, 3, 1, 2)\n",
      "(5, 4, 3, 2, 1)\n"
     ]
    }
   ],
   "source": [
    "#Exemplo estas são as permutações em E_5\n",
    "import itertools as it\n",
    "s=[1, 2, 3, 4, 5]\n",
    "SS= it.permutations(s)\n",
    "count = 0\n",
    "for x in SS:\n",
    "    print(str(x))\n",
    "    count+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "120\n"
     ]
    }
   ],
   "source": [
    "print(count)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ciclos e transposições\n",
    "\n",
    "Uma permutação $\\sigma \\in \\mathbb{S}_n$ deixa um elemento $k \\in E_n$ fixo se $\\sigma(k)=k$. Um $r$-ciclo é uma permutação $\\sigma$ que num subconjunto $\\{x_1,\\dots,x_r\\} \\in E_n$ satisfaz $\\sigma(x_i) = x_{i+1}$ e $\\sigma(x_r)=x_1$,\n",
    "e deixa os demais elementos fixos. Neste caso a notação \\sigma = \\begin{pmatrix} x_1 & x_2 & \\cdots & x_r \\end{pmatrix}$,\n",
    "é chamada notação em ciclos.\n",
    "\n",
    "### Exemplos\n",
    "Em $E_5$ a permutação $\\begin{pmatrix} 1 & 5 & 3 \\end{pmatrix}$ =$\\begin{pmatrix} 5 & 3 & 1 \\end{pmatrix}$=$\\begin{pmatrix} 3 & 1 & 5 \\end{pmatrix}$ = $\\begin{bmatrix} 5 & 2 & 1 & 4 & 3 \\end{bmatrix}$\n",
    "\n",
    "Um $2$-ciclo é chamado de transposição.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Representação matricial de uma permutação\n",
    "Uma permutação é uma bijeção\n",
    "$\\sigma: S_n \\to S_n$, em particular é uma relação binária em $S_n \\times S_n$, isto é, $i \\in S_n$ está relacionado com $j\\in S_n$ quando $\\sigma(i)=j$, podemos identificar esta relação com uma matriz $n\\times n$ com os coeficientes $a_{ij}=1$ se   $\\sigma(j)=i$ e $a_{ij} =0$ se  $\\sigma(i)\\not =j$.\n",
    "\n",
    "Por exemplo, a representação matricial de $$ \\sigma = \\left[\\begin{array}{cccc}\n",
    "3 & 2& 1 & 5 & 4 \\end{array} \\right]$$ é\n",
    "\n",
    "$$ M_\\sigma = \\begin{pmatrix} 0 & 0 & 1 & 0 & 0 \\\\\n",
    "0&1&0&0&0 \\\\\n",
    "1 & 0 & 0 & 0 & 0 \\\\\n",
    "0&0&0&0&1 \\\\\n",
    "0&0&0&1&0\n",
    "\\end{pmatrix} $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}