stable_roomates_final.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Stable Roomate Problem\n",
    "#### Algorithms and Data Structures Spring 2021\n",
    "##### Anna McNiff \n",
    "\n",
    "The stable roomate problem requires the division of an even sized set into pairs, optimizing the pairs so that a list of preferences is satisfied.  The stable roomate problem is a variation of the stable marriage problem, which requires the division of two sets into pairs, with each pair containing a member from each set.  A solution to the stable marriage problem was proposed in 1964 by David Gale and Llyod Shepley, in which members of one set 'propose' to members of the other set.  These proposals are issued in the order of preference of the proposer and conditionally accepted unless the recipient recieves a preferred proposal. This repeats until all participants have been matched.  This algorithm has been shown to consistently produce only the best outcome for the group issuing the proposals and the worst algorithm for the recipient group.  The stable roomate problem escapes this inherint inequity by removing the division between the two groups and allowing all individuals to propose to each other.  The rural hospital theorem, which addresses the question of matching doctors with residency programs, is a closely related problem to bothe the stable marrisge and stable roomates problems, but it differs in that it allows one party to accept multiple proposals, ie one hospital might accept multiple residents. This, coupled with the trend of strong preference towards urban hospitals, results in rural hospitals recieving fewer, less-preferred residents.  The rural hospital theorem shows that there is no stable alteration of the matching mechanism which could be made to reduce this inequity and distribute a higher quantity and quality of doctors to rural hospitals.  \n",
    "\n",
    "In 1985 Robert Irving proposed a solution to the stable roomate problem in \"An efficient algorithm for the \"stable roommates\" problem\" publised in the Journal of Algorithms. Irving's approach is divided into two stages.  In the first stage, a list of preferences is generated for each person being considered.  Also in the first stage, each person makes a \"proposal\" or potential match to the individual at the top of their preference list. If their proposal is rejected, meaning the recipient of the proposal has been proposed to by someone higher on their preference list, the rejected proposer iterates through the remainder of their preference list issuing proposals until one is accepted.  In cases where stable matching is possible, the first stage ends with each individual holding one proposal.  In cases where stable matching is impossible, one individual will be rejected by all other participants. The second stage of Irving's algorithm is composed of rotation eliminations, in which the list of potential matches is narrowed as individuals are matched and eliminated from consideration until all individuals are matched. The stable roomates problem also produces unresolvable cases when one individual has been rejected by all other individuals. \n",
    "\n",
    "There are many examples of situations which can be modeled by the stable roomate problem beyond assigning student housing, including student class registration, assignment of students to advanced work research projects, assignment of project or lab partners and more.  In addition, a real life application which arose this week would be the assignment of students to dinner tables for the senior Commencement dinner, for which all students were allowed to request three other students to be seated with.  This constitutes a two way matching problem where ideally groups of six students will have all mutually selected each other. Unfortunately for the Commencement planners, I doubt this was the case and this problem is considerably more complex than the version I model here. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random \n",
    "import time\n",
    "import math\n",
    "import pandas as pd\n",
    "import altair as alt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Dougie', 'Niko', 'Natan', 'Ciaran', 'Kevin', 'Lochlan']\n"
     ]
    }
   ],
   "source": [
    "babynames = pd.read_csv('babies_first_names_2010_2019.csv')\n",
    "babynames.head()\n",
    "list_of_names= []\n",
    "list_of_dicts = []\n",
    "def make_people(N):\n",
    "    \"\"\"Make a list of length N of People using names from a csv\"\"\"\n",
    "    for i in range(N):\n",
    "        indexn = random.randint(0,1000)\n",
    "        name = babynames.iloc[indexn][\"FirstForename\"]\n",
    "        list_of_names.append(name)\n",
    "    return list_of_names\n",
    "        \n",
    "\n",
    "def make_prefer(person, people, dictionary):\n",
    "    \"\"\"Generate a person's preferences \"\"\"\n",
    "    for i in people:\n",
    "        if i != person:\n",
    "            n = len(people)\n",
    "            score = random.randint(1,n)\n",
    "            dictionary[i]= score\n",
    "            return dictionary\n",
    "        \n",
    "def make_pref_d(people):\n",
    "    \"\"\"make preference dictionaries\"\"\"\n",
    "    dictionary = dict.fromkeys(people)\n",
    "    return dictionary\n",
    "\n",
    "def make_numbers(n):\n",
    "    \"\"\"Generate a list of numbers 1 to n\"\"\"\n",
    "    numbers = list(range(1, n))\n",
    "    return numbers\n",
    "\n",
    "def populate_pref_d_On(person, pref_list, numbers,n):\n",
    "    \"\"\"Populate a preference dictionary with random numbers\"\"\"\n",
    "    for key in pref_list:\n",
    "            if key == person:\n",
    "                pref_list[key] = 10000\n",
    "            else: \n",
    "                while len(numbers)> 0:\n",
    "                    number = random.choice(numbers)\n",
    "                    pref_list[key] = number\n",
    "                    numbers.remove(number)\n",
    "                if len(numbers)< 0:\n",
    "                    make_numbers(n)\n",
    "\n",
    "    return pref_list\n",
    "\n",
    "def populate_pref_d(person, pref_list, numbers,n):\n",
    "    \"\"\"Populate a preference dictionary with random numbers\"\"\"\n",
    "    for key in pref_list:\n",
    "            if key == person:\n",
    "                pref_list[key] = 10000\n",
    "            else: \n",
    "                number = random.choice(numbers)\n",
    "                pref_list[key] = number\n",
    "                numbers.remove(number)\n",
    "\n",
    "    return pref_list\n",
    "        \n",
    "        \n",
    "def make_list(people, n):\n",
    "    \"\"\"Make a list of dictionaries of preferences\"\"\"\n",
    "    for person in people:\n",
    "        pref_list = make_pref_d(people)\n",
    "        numbers = make_numbers(n)\n",
    "        populate_pref_d(person, pref_list, numbers,n)\n",
    "        numbers = list(range(1, n))\n",
    "        list_of_dicts.append(pref_list)\n",
    "        \n",
    "def make_listOn(people, n):\n",
    "    \"\"\"Make a list of dictionaries of preferences\"\"\"\n",
    "    #version for O(n) analysis - no prints etc\n",
    "    for person in people:\n",
    "        pref_list = make_pref_d(people)\n",
    "        numbers = make_numbers(n)\n",
    "        populate_pref_d_On(person, pref_list, numbers,n)\n",
    "        numbers = list(range(1, n))\n",
    "        list_of_dicts.append(pref_list)\n",
    "        \n",
    "def make_whole_thing(n):\n",
    "    \"\"\"Make People and preferences and populate preferences\"\"\"\n",
    "    make_numbers(n)\n",
    "    make_people(n)\n",
    "    make_pref_d(list_of_names)\n",
    "    print(list_of_names)\n",
    "    make_list(list_of_names, n)\n",
    "\n",
    "def make_whole_thingOn(n):\n",
    "    \"\"\"Make People and preferences and populate preferences\"\"\"\n",
    "    #version for O(n) analysis - no prints etc\n",
    "    make_numbers(n)\n",
    "    make_people(n)\n",
    "    make_pref_d(list_of_names)\n",
    "    make_listOn(list_of_names, n)\n",
    "    \n",
    "def make_blank(listname, n):\n",
    "    \"\"\"Take an empty list and fill it with n zeros\"\"\"\n",
    "    for i in range(n):\n",
    "        blank = 0 \n",
    "        listname.append(blank)\n",
    "test=[]\n",
    "#make_list(list_of_names)\n",
    "#list_of_names\n",
    "#make_pref_d(list_of_names)\n",
    "\n",
    "#list_of_dicts\n",
    "final = []\n",
    "prop2 = []\n",
    "propby = []\n",
    "all_lists=[final, prop2, propby]\n",
    "def make_all_blanks(listn, n):\n",
    "    \"\"\"Make all lists in a list blank\"\"\"\n",
    "    for i in listn:\n",
    "        make_blank(i,n)\n",
    "        \n",
    "def set_up(n):\n",
    "    \"\"\"Set everything up\"\"\"\n",
    "    make_whole_thing(n)\n",
    "    make_all_blanks(all_lists, n) \n",
    "    \n",
    "def set_upOn(n):\n",
    "    \"\"\"Set everything up for O(n)\"\"\"\n",
    "    make_whole_thingOn(n)\n",
    "    make_all_blanks(all_lists, n)\n",
    "    \n",
    "set_up(6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "top_list=[]\n",
    "\n",
    "\n",
    "def start_match1(listofdicts):\n",
    "    \"\"\"initial proposal to first person on preference list\"\"\"\n",
    "    #takes list of dictionarys as input\n",
    "    top_match = 0\n",
    "    for i in listofdicts:\n",
    "        for item in i: \n",
    "            value = i[item]\n",
    "            if value == 1: \n",
    "                    top_match = item\n",
    "                    #print(top_match)\n",
    "                    top_list.append(top_match)\n",
    "\n",
    "start_match1(list_of_dicts)\n",
    "data2={'Person': list_of_names,'Top_pick':top_list,'Rankings':list_of_dicts,\n",
    "       'top_match':top_list, 'Final':final, 'Proposed_to':prop2, 'Proposed_by':propby}\n",
    "matchesdf= pd.DataFrame(data2)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Person</th>\n",
       "      <th>Top_pick</th>\n",
       "      <th>Rankings</th>\n",
       "      <th>top_match</th>\n",
       "      <th>Final</th>\n",
       "      <th>Proposed_to</th>\n",
       "      <th>Proposed_by</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <td>0</td>\n",
       "      <td>Dougie</td>\n",
       "      <td>Niko</td>\n",
       "      <td>{'Dougie': 10000, 'Niko': 1, 'Natan': 4, 'Ciar...</td>\n",
       "      <td>Niko</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>1</td>\n",
       "      <td>Niko</td>\n",
       "      <td>Lochlan</td>\n",
       "      <td>{'Dougie': 2, 'Niko': 10000, 'Natan': 4, 'Ciar...</td>\n",
       "      <td>Lochlan</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>2</td>\n",
       "      <td>Natan</td>\n",
       "      <td>Lochlan</td>\n",
       "      <td>{'Dougie': 4, 'Niko': 2, 'Natan': 10000, 'Ciar...</td>\n",
       "      <td>Lochlan</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>3</td>\n",
       "      <td>Ciaran</td>\n",
       "      <td>Dougie</td>\n",
       "      <td>{'Dougie': 1, 'Niko': 5, 'Natan': 2, 'Ciaran':...</td>\n",
       "      <td>Dougie</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>4</td>\n",
       "      <td>Kevin</td>\n",
       "      <td>Dougie</td>\n",
       "      <td>{'Dougie': 1, 'Niko': 4, 'Natan': 2, 'Ciaran':...</td>\n",
       "      <td>Dougie</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>5</td>\n",
       "      <td>Lochlan</td>\n",
       "      <td>Niko</td>\n",
       "      <td>{'Dougie': 3, 'Niko': 1, 'Natan': 2, 'Ciaran':...</td>\n",
       "      <td>Niko</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    Person Top_pick                                           Rankings  \\\n",
       "0   Dougie     Niko  {'Dougie': 10000, 'Niko': 1, 'Natan': 4, 'Ciar...   \n",
       "1     Niko  Lochlan  {'Dougie': 2, 'Niko': 10000, 'Natan': 4, 'Ciar...   \n",
       "2    Natan  Lochlan  {'Dougie': 4, 'Niko': 2, 'Natan': 10000, 'Ciar...   \n",
       "3   Ciaran   Dougie  {'Dougie': 1, 'Niko': 5, 'Natan': 2, 'Ciaran':...   \n",
       "4    Kevin   Dougie  {'Dougie': 1, 'Niko': 4, 'Natan': 2, 'Ciaran':...   \n",
       "5  Lochlan     Niko  {'Dougie': 3, 'Niko': 1, 'Natan': 2, 'Ciaran':...   \n",
       "\n",
       "  top_match  Final  Proposed_to  Proposed_by  \n",
       "0      Niko      0            0            0  \n",
       "1   Lochlan      0            0            0  \n",
       "2   Lochlan      0            0            0  \n",
       "3    Dougie      0            0            0  \n",
       "4    Dougie      0            0            0  \n",
       "5      Niko      0            0            0  "
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "matchesdf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For convience of accessing matching information, I used a Pandas Data Frame to store preferences, proposals and matches. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true,
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Dougie\n",
      "{'Dougie': 10000, 'Niko': 1, 'Natan': 4, 'Ciaran': 3, 'Kevin': 5, 'Lochlan': 2}\n",
      "Dougie 's top match is Niko\n",
      "P2 Niko {'Dougie': 2, 'Niko': 10000, 'Natan': 4, 'Ciaran': 3, 'Kevin': 5, 'Lochlan': 1}\n",
      "P1 Dougie 2\n",
      "Niko accepts Dougie\n",
      "Niko\n",
      "{'Dougie': 2, 'Niko': 10000, 'Natan': 4, 'Ciaran': 3, 'Kevin': 5, 'Lochlan': 1}\n",
      "Niko 's top match is Lochlan\n",
      "P2 Lochlan {'Dougie': 3, 'Niko': 1, 'Natan': 2, 'Ciaran': 4, 'Kevin': 5, 'Lochlan': 10000}\n",
      "P1 Niko 1\n",
      "Lochlan accepts Niko\n",
      "Natan\n",
      "{'Dougie': 4, 'Niko': 2, 'Natan': 10000, 'Ciaran': 3, 'Kevin': 5, 'Lochlan': 1}\n",
      "Natan 's top match is Lochlan\n",
      "P2 Lochlan {'Dougie': 3, 'Niko': 1, 'Natan': 2, 'Ciaran': 4, 'Kevin': 5, 'Lochlan': 10000}\n",
      "P1 Natan 2\n",
      "Lochlan has already been proposed to by Niko\n",
      "Lochlan rejects Natan stays with Niko\n",
      "Natan 2 Niko 1\n",
      "Ciaran\n",
      "{'Dougie': 1, 'Niko': 5, 'Natan': 2, 'Ciaran': 10000, 'Kevin': 4, 'Lochlan': 3}\n",
      "Ciaran 's top match is Dougie\n",
      "P2 Dougie {'Dougie': 10000, 'Niko': 1, 'Natan': 4, 'Ciaran': 3, 'Kevin': 5, 'Lochlan': 2}\n",
      "P1 Ciaran 3\n",
      "Dougie accepts Ciaran\n",
      "Kevin\n",
      "{'Dougie': 1, 'Niko': 4, 'Natan': 2, 'Ciaran': 5, 'Kevin': 10000, 'Lochlan': 3}\n",
      "Kevin 's top match is Dougie\n",
      "P2 Dougie {'Dougie': 10000, 'Niko': 1, 'Natan': 4, 'Ciaran': 3, 'Kevin': 5, 'Lochlan': 2}\n",
      "P1 Kevin 5\n",
      "Dougie has already been proposed to by Ciaran\n",
      "Dougie rejects Kevin stays with Ciaran\n",
      "Kevin 5 Ciaran 3\n",
      "Lochlan\n",
      "{'Dougie': 3, 'Niko': 1, 'Natan': 2, 'Ciaran': 4, 'Kevin': 5, 'Lochlan': 10000}\n",
      "Lochlan 's top match is Niko\n",
      "P2 Niko {'Dougie': 2, 'Niko': 10000, 'Natan': 4, 'Ciaran': 3, 'Kevin': 5, 'Lochlan': 1}\n",
      "P1 Lochlan 1\n",
      "Niko has already been proposed to by Dougie\n",
      "Niko rejects Dougie accepts Lochlan\n",
      "Proposals Issued: {'Dougie': 0, 'Niko': 'Lochlan', 'Ciaran': 'Dougie', 'Lochlan': 'Niko'}\n",
      "0\n",
      "Dougie\n",
      "{'Dougie': 10000, 'Niko': 1, 'Natan': 4, 'Ciaran': 3, 'Kevin': 5, 'Lochlan': 2}\n",
      "Dougie 's top match is Lochlan\n",
      "P2 Lochlan {'Dougie': 3, 'Niko': 1, 'Natan': 2, 'Ciaran': 4, 'Kevin': 5, 'Lochlan': 10000}\n",
      "P1 Dougie 3\n",
      "Lochlan has already been proposed to by Niko\n",
      "Lochlan rejects Dougie stays with Niko\n",
      "Dougie 3 Niko 1\n",
      "here 2\n",
      "Dougie\n",
      "{'Dougie': 10000, 'Niko': 1, 'Natan': 4, 'Ciaran': 3, 'Kevin': 5, 'Lochlan': 2}\n",
      "Dougie 's top match is Ciaran\n",
      "P2 Ciaran {'Dougie': 1, 'Niko': 5, 'Natan': 2, 'Ciaran': 10000, 'Kevin': 4, 'Lochlan': 3}\n",
      "P1 Dougie 1\n",
      "Ciaran accepts Dougie\n",
      "here 3\n",
      "Dougie\n",
      "{'Dougie': 10000, 'Niko': 1, 'Natan': 4, 'Ciaran': 3, 'Kevin': 5, 'Lochlan': 2}\n",
      "Dougie 's top match is Natan\n",
      "P2 Natan {'Dougie': 4, 'Niko': 2, 'Natan': 10000, 'Ciaran': 3, 'Kevin': 5, 'Lochlan': 1}\n",
      "P1 Dougie 4\n",
      "Natan accepts Dougie\n",
      "here 4\n",
      "Lochlan\n",
      "Natan\n",
      "{'Dougie': 4, 'Niko': 2, 'Natan': 10000, 'Ciaran': 3, 'Kevin': 5, 'Lochlan': 1}\n",
      "Natan 's top match is Niko\n",
      "P2 Niko {'Dougie': 2, 'Niko': 10000, 'Natan': 4, 'Ciaran': 3, 'Kevin': 5, 'Lochlan': 1}\n",
      "P1 Natan 4\n",
      "Niko has already been proposed to by Lochlan\n",
      "Niko rejects Natan stays with Lochlan\n",
      "Natan 4 Lochlan 1\n",
      "here in else\n",
      "Natan\n",
      "{'Dougie': 4, 'Niko': 2, 'Natan': 10000, 'Ciaran': 3, 'Kevin': 5, 'Lochlan': 1}\n",
      "Natan 's top match is Ciaran\n",
      "P2 Ciaran {'Dougie': 1, 'Niko': 5, 'Natan': 2, 'Ciaran': 10000, 'Kevin': 4, 'Lochlan': 3}\n",
      "P1 Natan 2\n",
      "Ciaran accepts Natan\n",
      "here 10\n",
      "Dougie\n",
      "Kevin\n",
      "{'Dougie': 1, 'Niko': 4, 'Natan': 2, 'Ciaran': 5, 'Kevin': 10000, 'Lochlan': 3}\n",
      "Kevin 's top match is Natan\n",
      "P2 Natan {'Dougie': 4, 'Niko': 2, 'Natan': 10000, 'Ciaran': 3, 'Kevin': 5, 'Lochlan': 1}\n",
      "P1 Kevin 5\n",
      "Natan has already been proposed to by Dougie\n",
      "Natan rejects Kevin stays with Dougie\n",
      "Kevin 5 Dougie 4\n",
      "here in else\n",
      "Kevin\n",
      "{'Dougie': 1, 'Niko': 4, 'Natan': 2, 'Ciaran': 5, 'Kevin': 10000, 'Lochlan': 3}\n",
      "Kevin 's top match is Lochlan\n",
      "P2 Lochlan {'Dougie': 3, 'Niko': 1, 'Natan': 2, 'Ciaran': 4, 'Kevin': 5, 'Lochlan': 10000}\n",
      "P1 Kevin 5\n",
      "Lochlan has already been proposed to by Niko\n",
      "Lochlan rejects Kevin stays with Niko\n",
      "Kevin 5 Niko 1\n",
      "here 10\n",
      "Niko\n",
      "Proposals Issued: {'Dougie': 'Natan', 'Niko': 'Lochlan', 'Ciaran': 'Dougie', 'Lochlan': 'Niko', 'Natan': 'Ciaran'}\n",
      "Dougie Final Match is Natan\n",
      "Niko Final Match is Lochlan\n",
      "Ciaran Final Match is Dougie\n",
      "Lochlan Final Match is Niko\n",
      "Natan Final Match is Ciaran\n"
     ]
    }
   ],
   "source": [
    "top_list=[]\n",
    "\n",
    "def find_index(name):\n",
    "    \"\"\"Find the index of a Person given their name\"\"\"\n",
    "    index = 0\n",
    "    for item in matchesdf['Person']:\n",
    "        index = index +1 \n",
    "        if name == item:\n",
    "            return index-1\n",
    "def get_key(val, dictionary):\n",
    "    \"\"\"For a value in a dictionary, return the Key\"\"\"\n",
    "    for key, value in dictionary.items():\n",
    "         if val == value:\n",
    "                return key\n",
    "            \n",
    "        \n",
    "def first_proposals():\n",
    "    \"\"\"First round of proposals\"\"\"\n",
    "    #propose to person - person accepct if they hold no other proposals\n",
    "    # match is final when proposed to = proposed by ?\n",
    "    top_match = 0\n",
    "    for P1 in matchesdf['Person']:\n",
    "        print(P1)\n",
    "        P1index = find_index(P1)\n",
    "        print(P1index)\n",
    "        P2 = matchesdf.iloc[P1index][\"top_match\"]\n",
    "        print(P2)\n",
    "        P2index = find_index(P2)\n",
    "        print(P2index) \n",
    "        P2_pref = list_of_dicts[P2index]\n",
    "        print(P2_pref)\n",
    "        P1_score = P2_pref[P1]\n",
    "        print(P1, P1_score)\n",
    "        P3 = matchesdf.iloc[P2index][\"Proposed_by\"]\n",
    "        print(P3)\n",
    "        if P3 != 0: #accept or reject \n",
    "            P3_score = P2_pref[P3]\n",
    "            print(P3, P3_score)\n",
    "            if P3_score > P1_score:\n",
    "                P3 = P1 \n",
    "                propby[P1index]= P2\n",
    "        else: \n",
    "            prop2[P2index]= P2\n",
    "            propby[P1index]= P1\n",
    "\n",
    "                \n",
    "\n",
    "            \n",
    "proposals_issued ={}\n",
    "\n",
    "        \n",
    "def proposals(P1, N):\n",
    "    \"\"\"A person iterates through their prefence list issuing proposals\"\"\"\n",
    "    #These proposals are accepted or rejected based on the preferences of the recipients \n",
    "    top_match = 0\n",
    "    print(P1)\n",
    "    P1index = find_index(P1)\n",
    "    #print(P1index)  \n",
    "    P1pref = list_of_dicts[P1index]\n",
    "    print(P1pref)\n",
    "    P2 = get_key(N, P1pref)\n",
    "    print(P1,\"'s top match is\", P2)\n",
    "    P2index = find_index(P2)\n",
    "    #print(P2index) \n",
    "    P2_pref = list_of_dicts[P2index]\n",
    "    print(\"P2\",P2, P2_pref)\n",
    "    P1_score = P2_pref[P1]\n",
    "    print(\"P1\",P1, P1_score)\n",
    "    if P2 in proposals_issued.values():\n",
    "        P3 = get_key(P2, proposals_issued)\n",
    "        print(P2, \"has already been proposed to by\", P3)\n",
    "        P3_score = P2_pref[P3]\n",
    "        if P1_score < P3_score: \n",
    "            prop2[P1index]= P2  #P2 becomes P1's proposed to\n",
    "            propby[P2index] = P1 #P1 becomes P2's proposed by\n",
    "            proposals_issued[P1]=P2\n",
    "            proposals_issued[P3]=0\n",
    "            print(P2, \"rejects\", P3, \"accepts\", P1)\n",
    "        else:\n",
    "            print(P2, \"rejects\", P1, \"stays with\", P3)\n",
    "            print(P1, P1_score, P3, P3_score)\n",
    "    else: \n",
    "        prop2[P1index]= P2  #P2 becomes P1's proposed to\n",
    "        propby[P2index] = P1 #P1 becomes P2's proposed by\n",
    "        proposals_issued[P1]= P2\n",
    "        print(P2, \"accepts\",P1)\n",
    "    \n",
    "   \n",
    "                   \n",
    "                \n",
    "def proposing():\n",
    "    \"\"\"Each person in the dataframe issues proposals\"\"\"\n",
    "    for person in matchesdf['Person']: \n",
    "        proposals(person, 1) \n",
    "        \n",
    "        \n",
    "def proposing_next():\n",
    "    \"\"\"This represents Phase two, continued rounds of issuing proposals\"\"\"\n",
    "    #this is the less elegant version, which works for up to six people. \n",
    "    # I made this when my recursive version was not working as a back up, \n",
    "    # and I have included it in case the recursive version stops working again. \n",
    "    for person in matchesdf['Person']:\n",
    "        if person in proposals_issued:\n",
    "            check = proposals_issued.get(person)\n",
    "            print(check)\n",
    "            if check==0: \n",
    "                proposals(person, 2)\n",
    "                print(\"here 2\") #these print statements are to help track how the algorithm is progressing\n",
    "                if check==0:\n",
    "                    check = proposals_issued.get(person)\n",
    "                    proposals(person, 3)\n",
    "                    print(\"here 3\")\n",
    "                    if check==0:\n",
    "                        check = proposals_issued.get(person)\n",
    "                        proposals(person, 4)\n",
    "                        print(\"here 4\")\n",
    "                        if check==0:\n",
    "                            check = proposals_issued.get(person)\n",
    "                            proposals(person, 5)\n",
    "                            print(\"here 5\")\n",
    "                            if check==0:\n",
    "                                check = proposals_issued.get(person)\n",
    "                                proposals(person, 5)\n",
    "                                print(\"here 6\")\n",
    "        else:\n",
    "            proposals(person, 2)\n",
    "            print(\"here in else\") \n",
    "            check = proposals_issued.get(person)\n",
    "            if person in proposals_issued:\n",
    "                if check==0:\n",
    "                    check = proposals_issued.get(person)\n",
    "                    proposals(person, 3)\n",
    "                    print(\"here 3\") \n",
    "                    if person in proposals_issued:\n",
    "                        if check==0:\n",
    "                            check = proposals_issued.get(person)\n",
    "                            proposals(person, 4)\n",
    "                            print(\"here 4\")\n",
    "                            if person in proposals_issued:\n",
    "                                if check==0:\n",
    "                                    check = proposals_issued.get(person)\n",
    "                                    proposals(person, 5)\n",
    "                                    print(\"here 5\")\n",
    "                                    if person in proposals_issued:\n",
    "                                        if check==0:\n",
    "                                            check = proposals_issued.get(person)\n",
    "                                            proposals(person, 5)\n",
    "                                            print(\"here 6\")\n",
    "                                    else:\n",
    "                                        proposals(person, 5)\n",
    "                                        print(\"here 7\")\n",
    "                            else:\n",
    "                                proposals(person, 5)\n",
    "                                print(\"here 8\")\n",
    "                    else:\n",
    "                        proposals(person, 4)\n",
    "                        print(\"here 9\")\n",
    "            else:\n",
    "                proposals(person, 3)\n",
    "                print(\"here 10\")\n",
    "                \n",
    "number_prop = 1\n",
    "\n",
    "def check_again(person, num):\n",
    "    \"\"\"propose to next, for use in recursive match resolution\"\"\"\n",
    "    if person in proposals_issued:\n",
    "        check = proposals_issued.get(person)\n",
    "        #print(check)\n",
    "        if check==0: \n",
    "            proposals(person, num)\n",
    "            print(\"here\",num)\n",
    "            num = num+1\n",
    "            for i in range(1,len(final)):\n",
    "                check_again(person, i)    \n",
    "    else:\n",
    "        proposals(person, 2)\n",
    "        print(\"here in else\")\n",
    "        check = proposals_issued.get(person)\n",
    "        num = num+1\n",
    "        for i in range(1,len(final)):\n",
    "            check_again(person, i)\n",
    "\n",
    "def proposing_next2(num):\n",
    "    \"\"\"Recursive matching resolution\"\"\"\n",
    "    # Resolve matches by recursively issuing matches to \n",
    "    # increasingly lower preference individuals until \n",
    "    # matching is complete\n",
    "    for person in matchesdf['Person']:\n",
    "        for i in final:\n",
    "            check_again(person, num)\n",
    "            \n",
    "\n",
    "def finalize():\n",
    "    \"\"\"Finalize matches\"\"\"\n",
    "    for key in proposals_issued:\n",
    "        key_index = find_index(key)\n",
    "        value = proposals_issued[key]\n",
    "        if value != 0: \n",
    "            final[key_index]= value\n",
    "            print(key, \"Final Match is\", value)\n",
    "        if value == 0:\n",
    "            #This resolves an output issue\n",
    "            #if at the end of matching a person has no match, check and see if \n",
    "            #someone else has them as their final match, if so, then match them \n",
    "            if key in proposals_issued.values():\n",
    "                val = get_key(key,proposals_issued)\n",
    "                proposals_issued[key]= val \n",
    "                final[key_index]= val\n",
    "                print(key, \"Final Match is\", val)\n",
    "\n",
    "           \n",
    "            \n",
    "#def eliminations():\n",
    "def main():\n",
    "    proposing()\n",
    "    print(\"Proposals Issued:\", proposals_issued)\n",
    "    proposing_next() \n",
    "    print(\"Proposals Issued:\", proposals_issued)\n",
    "    finalize()\n",
    "    \n",
    "def main_recursive():\n",
    "    \"\"\"Version of main using recursion\"\"\"\n",
    "    #recursive version - was working, then wasn't working, now works(I think)\n",
    "    proposing()\n",
    "    print(\"Proposals Issued:\", proposals_issued)\n",
    "    proposing_next2(number_prop) \n",
    "    print(\"Proposals Issued:\", proposals_issued)\n",
    "    finalize()\n",
    "    \n",
    "main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If names are not mutually matched to each other - ie Antonio Final Match is Natan, Natan Final Match is Antonio, for all individuals- the instance is unresolvable. An example of what resolved matching looks like will be included as an HTML file. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below are versions of the above functions supposedly without any print statements for O(n) analysis.  Something is going on and there are still printed outputs. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def get_time_elapsed(function_name, threshold=0.05):\n",
    "    \"\"\" Return time taken to execute a function \"\"\"\n",
    "    # This is my code from Assignment 2 \n",
    "    timestorun = 1\n",
    "    while True:\n",
    "        start_time = time.time()              \n",
    "        for i in range(timestorun):\n",
    "            function_name()\n",
    "        end_time= time.time()\n",
    "        time_elapsed = end_time- start_time    \n",
    "        if  time_elapsed> threshold:\n",
    "            return time_elapsed/timestorun\n",
    "        else:\n",
    "            timestorun = timestorun*2\n",
    "            \n",
    "def proposals_for_On(P1, N):\n",
    "    \"\"\"version of proposals without print statements for O(n) analysis\"\"\"\n",
    "    top_match = 0 \n",
    "    P1index = find_index(P1)\n",
    "    P1pref=list_of_dicts[P1index]\n",
    "    P2=get_key(N,P1pref)\n",
    "    P2index = find_index(P2)\n",
    "    P2_pref = list_of_dicts[P2index]\n",
    "    P1_score = P2_pref[P1]\n",
    "    if P2 in proposals_issued.values():\n",
    "        P3 = get_key(P2, proposals_issued)\n",
    "        P3_score = P2_pref[P3]\n",
    "        prop2[P1index]= P2  #P2 becomes P1's proposed to\n",
    "        propby[P2index] = P1 #P1 becomes P2's proposed by\n",
    "        proposals_issued[P1]=P2\n",
    "        proposals_issued[P3]=0\n",
    "    else: \n",
    "        prop2[P1index]= P2  #P2 becomes P1's proposed to\n",
    "        propby[P2index] = P1 #P1 becomes P2's proposed by\n",
    "        proposals_issued[P1]= P2\n",
    "\n",
    "    \n",
    "def check_again_for_On(person, num):\n",
    "    \"\"\"version of check_again without print statements for O(n) analysis\"\"\"\n",
    "    if person in proposals_issued:\n",
    "        check = proposals_issued.get(person)\n",
    "        if check == 0: \n",
    "            proposals_for_On(person, num)\n",
    "            num = num+1\n",
    "            for i in range(1,len(final)):\n",
    "                check_again_for_On(person, i)\n",
    "    else:\n",
    "        proposals_for_On(person, 2)\n",
    "        check = proposals_issued.get(person)\n",
    "        num = num+1\n",
    "        for i in range(1,len(final)):\n",
    "            check_again_for_On(person, i)\n",
    "\n",
    "def proposing_On():\n",
    "    \"\"\"Version of proposing for O(n)\"\"\"\n",
    "    for person in matchesdf['Person']: \n",
    "        proposals_for_On(person, 1) \n",
    "\n",
    "def proposing_next2_On(num):\n",
    "    \"\"\"version of proposing_next2 for O(n)\"\"\"\n",
    "    for person in matchesdf['Person']: \n",
    "        for i in final:\n",
    "            check_again_for_On(person,num)\n",
    "numberon=1            \n",
    "def for_On():\n",
    "    proposing_On()\n",
    "    proposing_next2_On(numberon)\n",
    "    #print(\"done\")\n",
    "\n",
    "def function(n):\n",
    "    set_upOn(n)\n",
    "    for_On()\n",
    "    \n",
    "function(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.8994390964508057,\n",
       " 1.0971031188964844,\n",
       " 1.381655216217041,\n",
       " 5.851430892944336,\n",
       " 20.578261137008667]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "my_n_list=[10,50,100,500,1000]\n",
    "my_times_list=[get_time_elapsed(lambda:function(n)) for n in my_n_list]\n",
    "my_times_list_names = [get_time_elapsed(lambda:set_upOn(n)) for n in my_n_list]\n",
    "my_times_list\n",
    "my_times_list_names"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Time to Match</th>\n",
       "      <th>Time to Make Names</th>\n",
       "      <th>Number of People</th>\n",
       "      <th>Adjusted Time to Match</th>\n",
       "      <th>n squared</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <td>0</td>\n",
       "      <td>0.422959</td>\n",
       "      <td>0.899439</td>\n",
       "      <td>10</td>\n",
       "      <td>-0.476480</td>\n",
       "      <td>0.0015</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>1</td>\n",
       "      <td>0.434831</td>\n",
       "      <td>1.097103</td>\n",
       "      <td>50</td>\n",
       "      <td>-0.662272</td>\n",
       "      <td>0.0375</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>2</td>\n",
       "      <td>0.595892</td>\n",
       "      <td>1.381655</td>\n",
       "      <td>100</td>\n",
       "      <td>-0.785763</td>\n",
       "      <td>0.1500</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>3</td>\n",
       "      <td>3.246419</td>\n",
       "      <td>5.851431</td>\n",
       "      <td>500</td>\n",
       "      <td>-2.605012</td>\n",
       "      <td>3.7500</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>4</td>\n",
       "      <td>13.612571</td>\n",
       "      <td>20.578261</td>\n",
       "      <td>1000</td>\n",
       "      <td>-6.965690</td>\n",
       "      <td>15.0000</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   Time to Match  Time to Make Names  Number of People  \\\n",
       "0       0.422959            0.899439                10   \n",
       "1       0.434831            1.097103                50   \n",
       "2       0.595892            1.381655               100   \n",
       "3       3.246419            5.851431               500   \n",
       "4      13.612571           20.578261              1000   \n",
       "\n",
       "   Adjusted Time to Match  n squared  \n",
       "0               -0.476480     0.0015  \n",
       "1               -0.662272     0.0375  \n",
       "2               -0.785763     0.1500  \n",
       "3               -2.605012     3.7500  \n",
       "4               -6.965690    15.0000  "
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "constant = .000015\n",
    "data3={'Time to Match': my_times_list,'Time to Make Names':my_times_list_names, 'Number of People':my_n_list}\n",
    "Ordern= pd.DataFrame(data3)\n",
    "Ordern['Adjusted Time to Match']=Ordern['Time to Match']-Ordern['Time to Make Names']\n",
    "Ordern['n squared']=constant*Ordern['Number of People']*Ordern['Number of People']\n",
    "Ordern"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "<div id=\"altair-viz-e694980d42064d6a8ae896853a477c41\"></div>\n",
       "<script type=\"text/javascript\">\n",
       "  (function(spec, embedOpt){\n",
       "    const outputDiv = document.getElementById(\"altair-viz-e694980d42064d6a8ae896853a477c41\");\n",
       "    const paths = {\n",
       "      \"vega\": \"https://cdn.jsdelivr.net/npm//vega@5?noext\",\n",
       "      \"vega-lib\": \"https://cdn.jsdelivr.net/npm//vega-lib?noext\",\n",
       "      \"vega-lite\": \"https://cdn.jsdelivr.net/npm//vega-lite@4.0.2?noext\",\n",
       "      \"vega-embed\": \"https://cdn.jsdelivr.net/npm//vega-embed@6?noext\",\n",
       "    };\n",
       "\n",
       "    function loadScript(lib) {\n",
       "      return new Promise(function(resolve, reject) {\n",
       "        var s = document.createElement('script');\n",
       "        s.src = paths[lib];\n",
       "        s.async = true;\n",
       "        s.onload = () => resolve(paths[lib]);\n",
       "        s.onerror = () => reject(`Error loading script: ${paths[lib]}`);\n",
       "        document.getElementsByTagName(\"head\")[0].appendChild(s);\n",
       "      });\n",
       "    }\n",
       "\n",
       "    function showError(err) {\n",
       "      outputDiv.innerHTML = `<div class=\"error\" style=\"color:red;\">${err}</div>`;\n",
       "      throw err;\n",
       "    }\n",
       "\n",
       "    function displayChart(vegaEmbed) {\n",
       "      vegaEmbed(outputDiv, spec, embedOpt)\n",
       "        .catch(err => showError(`Javascript Error: ${err.message}<br>This usually means there's a typo in your chart specification. See the javascript console for the full traceback.`));\n",
       "    }\n",
       "\n",
       "    if(typeof define === \"function\" && define.amd) {\n",
       "      requirejs.config({paths});\n",
       "      require([\"vega-embed\"], displayChart, err => showError(`Error loading script: ${err.message}`));\n",
       "    } else if (typeof vegaEmbed === \"function\") {\n",
       "      displayChart(vegaEmbed);\n",
       "    } else {\n",
       "      loadScript(\"vega\")\n",
       "        .then(() => loadScript(\"vega-lite\"))\n",
       "        .then(() => loadScript(\"vega-embed\"))\n",
       "        .catch(showError)\n",
       "        .then(() => displayChart(vegaEmbed));\n",
       "    }\n",
       "  })({\"config\": {\"view\": {\"continuousWidth\": 400, \"continuousHeight\": 300}}, \"hconcat\": [{\"layer\": [{\"mark\": \"point\", \"encoding\": {\"x\": {\"type\": \"quantitative\", \"field\": \"Number of People\"}, \"y\": {\"type\": \"quantitative\", \"field\": \"Time to Match\"}}}, {\"mark\": {\"type\": \"line\", \"color\": \"red\", \"opacity\": 0.4}, \"encoding\": {\"x\": {\"type\": \"quantitative\", \"field\": \"Number of People\"}, \"y\": {\"type\": \"quantitative\", \"field\": \"n squared\"}}}]}, {\"mark\": \"point\", \"encoding\": {\"x\": {\"type\": \"quantitative\", \"field\": \"Number of People\"}, \"y\": {\"type\": \"quantitative\", \"field\": \"Adjusted Time to Match\"}}}], \"data\": {\"name\": \"data-c65ef5deca9435b7e2763a54cf404c22\"}, \"$schema\": \"https://vega.github.io/schema/vega-lite/v4.0.2.json\", \"datasets\": {\"data-c65ef5deca9435b7e2763a54cf404c22\": [{\"Time to Match\": 0.4229590892791748, \"Time to Make Names\": 0.8994390964508057, \"Number of People\": 10, \"Adjusted Time to Match\": -0.47648000717163086, \"n squared\": 0.0015}, {\"Time to Match\": 0.434830904006958, \"Time to Make Names\": 1.0971031188964844, \"Number of People\": 50, \"Adjusted Time to Match\": -0.6622722148895264, \"n squared\": 0.0375}, {\"Time to Match\": 0.5958919525146484, \"Time to Make Names\": 1.381655216217041, \"Number of People\": 100, \"Adjusted Time to Match\": -0.7857632637023926, \"n squared\": 0.15}, {\"Time to Match\": 3.2464189529418945, \"Time to Make Names\": 5.851430892944336, \"Number of People\": 500, \"Adjusted Time to Match\": -2.6050119400024414, \"n squared\": 3.7500000000000004}, {\"Time to Match\": 13.612571001052856, \"Time to Make Names\": 20.578261137008667, \"Number of People\": 1000, \"Adjusted Time to Match\": -6.9656901359558105, \"n squared\": 15.000000000000002}]}}, {\"mode\": \"vega-lite\"});\n",
       "</script>"
      ],
      "text/plain": [
       "alt.HConcatChart(...)"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "chart = alt.Chart(Ordern).mark_point().encode(x='Number of People', y='Time to Match')\n",
    "#chart+chart.transform_regression('Number of People', 'Time to Match',method=\"linear\"\n",
    "#).mark_line(color=\"red\") #fit a linear regression line to chart\n",
    "chart2 = alt.Chart(Ordern).mark_line(opacity=0.4, color='red').encode(x='Number of People', y='n squared')\n",
    "chart3 = alt.Chart(Ordern).mark_point().encode(x='Number of People', y='Adjusted Time to Match')\n",
    "chart+chart2 |chart3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As shown in the graph on the right above, my matching algorithm roughly follows exponential growth, implying Order n squared behaviour. The graph on the right displays the Adjusted Time to run the matching algorithm, subtracting the time it takes to run the necessary setup functions for a set of size n. Interestingly, at least on my computer, it's currently taking longer to retreive the names and set up outside of the combined function, so this graph is not useful for analysis. I tried to run this with bigger numbers for a more accurate analysis but Jupyter froze completley.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Resources\n",
    "https://towardsdatascience.com/gale-shapley-algorithm-simply-explained-caa344e643c2 \n",
    "https://en.wikipedia.org/wiki/Stable_roommates_problem\n",
    "https://en.wikipedia.org/wiki/Stable_marriage_problem\n",
    "https://uvacs2102.github.io/docs/roomates.pdf \n",
    "https://www.geeksforgeeks.org/stable-marriage-problem/ \n",
    "https://gist.github.com/joyrexus/9967709\n",
    "https://www.nrscotland.gov.uk/statistics-and-data/statistics/statistics-by-theme/vital-events/names/babies-first-names/babies-first-names-summary-records-comma-separated-value-csv-format"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}