Lookup Without Replacement.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider two vectors, e.g. **L**: `'abacba'` and **R**: `'baabaac'`.\n",
    "By now, you should know about dyadic `⍳`: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">2 1 1 2 1 1 4\n",
       "</span>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L←'abacba'\n",
    "R←'baabaac'\n",
    "L⍳R"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That finds first location in **L** of each element in **R**.\n",
    "\n",
    "However, what if we wanted the first b in **R** to \"consume\" the first b in **L** so that the second b in **R** would have to contend with the index of the second b in **L**?\n",
    "\n",
    "That is, we want some function which gives `2 1 3 5 6 7 4`. You could call it \"iota without replacement\". As, in a sense, the iota *progresses* through **L** as it finds element from **R**, it is also known in APL circles as \"progressive dyadic iota\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">2 1 3 5 6 7 4\n",
       "</span>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'a1' 'b1' 'a2' 'c1' 'b2' 'a3' ⍳ 'b1' 'a1' 'a2' 'b2' 'a3' 'a4' 'c1'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, because we numbered the as (which otherwise all match each other) and the bs, the right pairs get matched up. \n",
    "\n",
    "While `⍋` gives us the indices that will sort, `⍋⍋` gives us the positions that each element will occupy in the sorted result."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">a b a c b a\n",
       "1 2 1 4 2 1\n",
       "1 4 2 6 5 3\n",
       "</span>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "↑L (L⍳L) (⍋⍋L⍳L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first line is the data and the second is the indices of the first occurrences (i.e. all identical items will get the same index). The third line is the position that each will occupy when sorted. That means that identical elements get consecutive positions.\n",
    "\n",
    "E.g. you can see that the first b gets 4 (because there are 3 as) and the second gets 5."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can label both vectors in this way:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 2 2 1 2 2 7\n",
       "</span>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(L⍳L)⍳(R⍳R)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This almost solves the problem (although it might not look like it), but this labelling depends on both the order and the frequency of the elements in a vector. However, we need both vectors to be labelled in the same way, i.e the first `a` in each vector will get same label, and the second `b` in each will also get matching labels."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since we're going to look up elements of **R** in **L** anyway, we can use indices into **L** (that is `L⍳R`) instead of the lookup of **R** into itself (`R⍳R`) This ensures that elements of **R** are labelled with \"L's labelling system\". "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">a b a c b a\n",
       "1 2 1 4 2 1\n",
       "1 4 2 6 5 3\n",
       "</span>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "↑L (L⍳L) (⍋⍋L⍳L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">b a a b a a c\n",
       "2 1 1 2 1 1 4\n",
       "5 1 2 6 3 4 7\n",
       "</span>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "↑R (L⍳R) (⍋⍋L⍳R)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The only problem that remains is that **L** and **R** have their elements with different frequencies. The first b of **R** is labelled 5, whereas the first b of **L** is labelled 4. This is because **L** has one less a."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To solve this we need the second argument of each `⍳` to have the same number of each element when labelling both **L** and **R**. The easiest way to do this is with `L⍪R` and `R⍪L`. `⍪` is used instead of `,` so that the method can be used for higher rank arrays."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 8 2 12 9 3 10 4 5 11 6 7 13\n",
       "</span>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⍋⍋L⍳L,R"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">8 1 2 9 3 4 12 5 10 6 13 11 7\n",
       "</span>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⍋⍋L⍳R,L"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, now we are working in precisely the same labelling scheme for both **L** and **R**, we just need use `↑` to remove the unneeded elements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 8 2 12 9 3\n",
       "</span>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(≢L)↑⍋⍋L⍳L⍪R"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">8 1 2 9 3 4 12\n",
       "</span>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(≢R)↑⍋⍋L⍳R⍪L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">2 1 3 5 6 7 4\n",
       "</span>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "((≢L)↑⍋⍋L⍳L⍪R)⍳((≢R)↑⍋⍋L⍳R⍪L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we can define this function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "f←{((≢⍺)↑⍋⍋⍺⍳⍺⍪⍵)⍳((≢⍵)↑⍋⍋⍺⍳⍵⍪⍺)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A use case of this function is in a first-come, first-served queue. For example you might have First Class, Premium, Business, and Economy seats on a plane. This function will allocate seats based on which class was ordered."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lets say we have a plane: `'11bbbpeepee'` where 1 is first class, p is premium, b is business, and e is economy. And we have a bunch of customers coming to buy seats: `'bbepbeppe1ee'`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">3 4 7 6 5 8 9 12 10 1 11 12\n",
       "</span>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'11bbbpeepee' f 'bbepbeppe1ee'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Person number 1 gets seat 3, person number 3 gets seat 7, and so on. People  8 and 12 however cannot get a seat, because all of the seats of their type have been allocated already. This is indicated by the result `12` which is out of the bounds of plane (length-11)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Dyalog APL",
   "language": "apl",
   "name": "dyalog-kernel"
  },
  "language_info": {
   "file_extension": ".apl",
   "mimetype": "text/apl",
   "name": "APL"
  },
  "tryapl": {
   "category": "Interesting Explorations",
   "description": "Lookup Without Replacement (a.k.a. Dynamic Progressive Iota)",
   "name": "Lookup Without Replacement"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}