{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "INFO: Loading help data...\n"
     ]
    }
   ],
   "source": [
    "using PyPlot\n",
    "using StatsBase # has the countmap function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "rsk (generic function with 1 method)"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function rsk(seq)\n",
    "    ## Input: seq ... a sequence of whole numbers (all >= 0)\n",
    "    ## Output: A partition P capturing large scale sorting structure\n",
    "\n",
    "    n  = length(seq)\n",
    "    m1 = iround(2*sqrt(n))\n",
    "    m2 = iround(2*sqrt(n))\n",
    "    P  = fill(NaN, m1, m2)\n",
    "\n",
    "    for i = 1:n\n",
    "        nw = seq[i]\n",
    "\n",
    "        for j = 1:n\n",
    "            if j > m2\n",
    "                P = hcat(P, fill(NaN, m1, m2))\n",
    "                m2 = 2*m2\n",
    "            end\n",
    "            k = 1\n",
    "            while P[k,j] <= nw\n",
    "                k += 1\n",
    "                if k > m1\n",
    "                    P  = vcat(P, fill(NaN, m1, m2))\n",
    "                    m1 = 2*m1\n",
    "                    break\n",
    "                end\n",
    "            end\n",
    "\n",
    "            old = P[k,j]\n",
    "            P[k,j] = nw\n",
    "            nw = old\n",
    "            if isnan(nw)\n",
    "                break\n",
    "            end\n",
    "        end\n",
    "    end\n",
    "\n",
    "    return P\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5x5 Array{Float64,2}:\n",
       "   1.0    3.0    4.0  NaN  NaN\n",
       "   2.0  NaN    NaN    NaN  NaN\n",
       "   5.0  NaN    NaN    NaN  NaN\n",
       "   6.0  NaN    NaN    NaN  NaN\n",
       " NaN    NaN    NaN    NaN  NaN"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rsk(randperm(6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "n = 1000\n",
    "p = randperm(n)\n",
    "pygui(true) # Necessary for animation effect\n",
    "clf()\n",
    "xlim(0,60)\n",
    "ylim(0,60)\n",
    "for i = 100:5:n\n",
    "    plt.imshow(rsk(p[1:i]), interpolation = \"none\")\n",
    "    sleep(0.001)\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Count frequencies of shapes of the RSK for each of the `6!=720` permutations of `{1,2,3,4,5,6}`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Dict{Array{Int64,1},Int64} with 11 entries:\n",
       "  [3,3,0,0,0]           => 25\n",
       "  [5,1,0,0,0]           => 25\n",
       "  [2,2,2,0,0]           => 25\n",
       "  [4,2,0,0,0]           => 81\n",
       "  [1,1,1,1,1,1,0,0,0,0] => 1\n",
       "  [3,1,1,1,0]           => 100\n",
       "  [2,1,1,1,1]           => 25\n",
       "  [2,2,1,1,0]           => 81\n",
       "  [6,0,0,0,0]           => 1\n",
       "  [3,2,1,0,0]           => 256\n",
       "  [4,1,1,0,0]           => 100"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "countmap([vec(sum(rsk(p) .> 0, 2)) for p in permutations(1:6)])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.3.7-pre",
   "language": "julia",
   "name": "julia 0.3"
  },
  "language_info": {
   "name": "julia",
   "version": "0.3.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}