安定結婚問題

安定結婚問題.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 安定結婚問題\n",
    "\n",
    "* 参考書 [入門オペレーションズリサーチ](https://www.amazon.co.jp/dp/4486017447)\n",
    "* 第10章 駆け落ちしないペアを作る 安定結婚問題\n",
    "* (p.130) 10.4 男性からプロポーズする"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'A': ['x', 'y', 'z'],\n",
       " 'B': ['x', 'z', 'y'],\n",
       " 'C': ['y', 'x', 'z'],\n",
       " 'x': ['B', 'A', 'C'],\n",
       " 'y': ['A', 'C', 'B'],\n",
       " 'z': ['B', 'C', 'A']}"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 各メンバーの希望リストを作成。\n",
    "# ここでは、A,B,Cを男性、x,y,zを女性とする。\n",
    "P = {}\n",
    "P['A'] = ['x','y','z']\n",
    "P['B'] = ['x','z','y']\n",
    "P['C'] = ['y','x','z']\n",
    "P['x'] = ['B','A','C']\n",
    "P['y'] = ['A','C','B']\n",
    "P['z'] = ['B','C','A']\n",
    "P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'A': 0, 'B': 0, 'C': 0}"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 男性側からプロポーズすることとし、何番目の希望を見ているかを保持するインデックスを作成する。\n",
    "# （リストの添字に使うため、ゼロオリジンとする）\n",
    "I = {}\n",
    "I['A'] = 0\n",
    "I['B'] = 0\n",
    "I['C'] = 0\n",
    "I"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 成立したペアを双方向（a->b, b->a）で保持する辞書。最初は空。\n",
    "A = {}\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'B': 'y', 'y': 'B', 'A': 'x', 'x': 'A'}\n"
     ]
    }
   ],
   "source": [
    "# ペアを登録するメソッド\n",
    "def add_pair(a,m,w):\n",
    "    a[m] = w\n",
    "    a[w] = m\n",
    "    return a\n",
    "\n",
    "print(add_pair({'B': 'y', 'y': 'B'}, 'A', 'x'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'B': 'y', 'y': 'B'}\n"
     ]
    }
   ],
   "source": [
    "# ペアを解消するメソッド\n",
    "def break_pair(a,m,w):\n",
    "    del a[m]\n",
    "    del a[w]\n",
    "    return a\n",
    "\n",
    "print(break_pair({'x': 'A', 'A': 'x', 'B': 'y', 'y': 'B'}, 'A', 'x'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "rank: A -> x, 0\n",
      "rank: x -> A, 1\n",
      "rank: x -> B, 0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# aさんにとってbさんが何番目の希望かを取得するメソッド\n",
    "def rank(p,a,b):\n",
    "    if a not in p:\n",
    "        return None\n",
    "    print(\"rank: {} -> {}, {}\".format(a, b, p[a].index(b)))\n",
    "    return p[a].index(b)\n",
    "\n",
    "rank(P, 'A', 'x')\n",
    "rank(P, 'x', 'A')\n",
    "rank(P, 'x', 'B')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# mさんにとって次の希望者を取得する\n",
    "# （インデックスが増えるので冪等ではない）\n",
    "def pick_next(p,a,i,m):\n",
    "    w = p[m][i[m]]\n",
    "    print(\"pick_next: {}:{}, {}\".format(m, i[m], w))\n",
    "    i[m] += 1\n",
    "    return w\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pick_next: A:0, x\n",
      "rank: x -> A, 1\n",
      "rank: x -> A, 1\n",
      "{'x': 'A', 'A': 'x'}\n"
     ]
    }
   ],
   "source": [
    "# mさんの次の希望者を取得し、\n",
    "# 可能であればペアを登録、または更新する。\n",
    "def step_next(p, a, i, m):\n",
    "    # mさんの次の希望者を取得する。ここではcさんとする。\n",
    "    c = pick_next(p, a, i, m)\n",
    "\n",
    "    # まだcさんに相手がいなければ、mさんとペア登録する。\n",
    "    if c not in a:\n",
    "        a = add_pair(a, c, m)\n",
    "    # 既にcさんに相手がいた場合、既存の相手とmさんの希望順を比較、\n",
    "    # mさんの希望順の方が高ければ、既存の相手とのペアを解消し、\n",
    "    # mさんとペア登録する。\n",
    "    if c in a:\n",
    "        r1 = rank(p, c, a[c])\n",
    "        r2 = rank(p, c, m)\n",
    "        if r2 < r1:\n",
    "            a = break_pair(a, c, a[c])\n",
    "            a = add_pair(a, c, m)\n",
    "\n",
    "step_next(P, A, I, 'A')\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pick_next: B:0, x\n",
      "rank: x -> A, 1\n",
      "rank: x -> B, 0\n",
      "{'x': 'B', 'B': 'x'}\n"
     ]
    }
   ],
   "source": [
    "step_next(P, A, I, 'B')\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pick_next: C:0, y\n",
      "rank: y -> C, 1\n",
      "rank: y -> C, 1\n",
      "{'x': 'B', 'B': 'x', 'y': 'C', 'C': 'y'}\n"
     ]
    }
   ],
   "source": [
    "step_next(P, A, I, 'C')\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pick_next: A:1, y\n",
      "rank: y -> C, 1\n",
      "rank: y -> A, 0\n",
      "{'x': 'B', 'B': 'x', 'y': 'A', 'A': 'y'}\n"
     ]
    }
   ],
   "source": [
    "step_next(P, A, I, 'A')\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pick_next: C:1, x\n",
      "rank: x -> B, 0\n",
      "rank: x -> C, 2\n",
      "{'x': 'B', 'B': 'x', 'y': 'A', 'A': 'y'}\n"
     ]
    }
   ],
   "source": [
    "step_next(P, A, I, 'C')\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pick_next: C:2, z\n",
      "rank: z -> C, 1\n",
      "rank: z -> C, 1\n",
      "{'x': 'B', 'B': 'x', 'y': 'A', 'A': 'y', 'z': 'C', 'C': 'z'}\n"
     ]
    }
   ],
   "source": [
    "step_next(P, A, I, 'C')\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A: ['x', 'y', 'z']\n",
      "B: ['x', 'z', 'y']\n",
      "C: ['y', 'x', 'z']\n",
      "x: ['B', 'A', 'C']\n",
      "y: ['A', 'C', 'B']\n",
      "z: ['B', 'C', 'A']\n",
      "A - y\n",
      "B - x\n",
      "C - z\n"
     ]
    }
   ],
   "source": [
    "# 最初の希望リストと結果を表示\n",
    "for p in P:\n",
    "    print(\"{}: {}\".format(p, P[p]))\n",
    "for m in I:\n",
    "    print(\"{} - {}\".format(m, A[m]))"
   ]
  },
  {
   "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}