DA_Algorithms.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:9418b299b920a9bbf553e92b84c16dd2eeb107f31528cb39e89a2f2b73cbd474"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#!/usr/bin/python\n",
      "#-*- encoding: utf-8 -*-\n",
      "# Quantitative Economics Web: http://quant-econ.net/py/index.html\n",
      "\n",
      "from __future__ import division\n",
      "import math\n",
      "import functools  #for python3\n",
      "from random import uniform, normalvariate, shuffle\n",
      "import numpy as np\n",
      "import time\n",
      "\n",
      "\n",
      "class CustomConditionError(Exception):\n",
      "    def __init__(self, message):\n",
      "        self.message = message\n",
      "\n",
      "\n",
      "def gale_shapley(applicant_prefers_input, host_prefers_input, **kwargs):\n",
      "     unmatch = kwargs.get('unmatch', True)\n",
      "\n",
      "     # \u9078\u597d\u8868\u306e\u578b\u30c1\u30a7\u30c3\u30af\u3002list\u306a\u3089numpy\u3078\u5909\u63db\n",
      "     applicant_preferences = np.asarray(applicant_prefers_input, dtype=int)\n",
      "     host_preferences = np.asarray(host_prefers_input, dtype=int)\n",
      "\n",
      "     # \u9078\u597d\u8868\u306e\u884c\u5217\u6570\u3092\u30c1\u30a7\u30c3\u30af\n",
      "     app_row, app_col = applicant_preferences.shape\n",
      "     host_row, host_col = host_preferences.shape\n",
      "\n",
      "     # unmatch\u30de\u30fc\u30af\u304c\u5165\u529b\u3055\u308c\u3066\u3044\u306a\u3044\u6642\u306f\u3001\u9078\u597d\u8868\u306e\u5217\u306e\u6700\u5f8c\u306bunmatch\u5217\u3092\u3064\u304f\u308b\n",
      "     if not unmatch:\n",
      "          dummy_host = np.repeat(app_col+1, app_row)\n",
      "          dummy_applicant = np.repeat(host_col+1, host_row)\n",
      "          applicant_preferences = np.c_[applicant_preferences, dummy_host]\n",
      "          host_preferences = np.c_[host_preferences, dummy_applicant]\n",
      "          app_col += 1\n",
      "          host_col += 1\n",
      "\n",
      "\n",
      "     if (app_row != host_col-1) or (host_row != app_col-1):\n",
      "          raise CustomConditionError(\"\u9078\u597d\u8868\u306e\u884c\u5217\u6570\u304c\u4e0d\u6b63\u3067\u3059\")\n",
      "     \n",
      "     applicant_unmatched_mark = app_col-1\n",
      "     host_unmatched_mark = host_col-1\n",
      "\n",
      "     # \u30bd\u30fc\u30c8\n",
      "     host_preferences = np.argsort(host_preferences, axis=-1)\n",
      "\n",
      "     # \u672a\u30de\u30c3\u30c1\u30f3\u30b0\u8005\u306e\u30ea\u30b9\u30c8\n",
      "     stack = list(range(app_row))\n",
      "\n",
      "     # \u30de\u30c3\u30c1\u30f3\u30b0\u3092\u5165\u308c\u308b\uff08\u521d\u671f\u5024\u306f\u672a\u30de\u30c3\u30c1\u30f3\u30b0flag\uff09\n",
      "     applicant_matchings = np.repeat(applicant_unmatched_mark, app_row)\n",
      "     host_matchings = np.repeat(host_unmatched_mark, host_row)\n",
      "\n",
      "\n",
      "     # \u30e1\u30a4\u30f3\u30eb\u30fc\u30d7\n",
      "     next_start = np.zeros(app_row, dtype=int)\n",
      "     while len(stack) > 0:\n",
      "          # \u30b9\u30bf\u30c3\u30af\u304b\u30891\u4eba\u5fdc\u52df\u8005\u3092\u53d6\u308a\u51fa\u3059\n",
      "          applicant = stack.pop()\n",
      "\n",
      "          # \u53d6\u308a\u51fa\u3057\u305f\u5fdc\u52df\u8005\u306e\u9078\u597d\u8868\n",
      "          applicant_preference = applicant_preferences[applicant]\n",
      "\n",
      "          # \u9078\u597d\u8868\u306e\u4e0a\u304b\u3089\u9806\u756a\u306b\u30d7\u30ed\u30dd\u30fc\u30ba\n",
      "          for index, host in enumerate(applicant_preference[next_start[applicant]:]):\n",
      "               # unmatched_mark\u307e\u3067applicant\u304c\u30de\u30c3\u30c1\u30f3\u30b0\u3067\u304d\u306a\u3051\u308c\u3070\u3001\u30a2\u30f3\u30de\u30c3\u30c1\n",
      "               if host == applicant_unmatched_mark:\n",
      "                    break\n",
      "\n",
      "               # \u30d7\u30ed\u30dd\u30fc\u30ba\u3059\u308b\u76f8\u624b\u306e\u9078\u597d\u8868\n",
      "               host_preference = host_preferences[host]\n",
      "\n",
      "               # \u76f8\u624b\u306e\u9078\u597d\u8868\u3067\u3001\u5fdc\u52df\u8005\u3068\u73fe\u5728\u306e\u30de\u30c3\u30c1\u30f3\u30b0\u76f8\u624b\u306e\u3069\u3061\u3089\u304c\u9806\u4f4d\u304c\u9ad8\u3044\u306e\u304b\u6bd4\u8f03\u3059\u308b\n",
      "               rank_applicant = host_preference[applicant]\n",
      "               matched = host_matchings[host]\n",
      "               rank_matched = host_preference[matched]\n",
      "               \n",
      "               # \u3082\u3057\u53d7\u3051\u5165\u308c\u5074\u304c\u65b0\u3057\u3044\u5fdc\u52df\u8005\u306e\u65b9\u3092\u597d\u3080\u306a\u3089\n",
      "               if rank_matched > rank_applicant:\n",
      "                    applicant_matchings[applicant] = host\n",
      "                    host_matchings[host] = applicant\n",
      "\n",
      "                    # \u65e2\u306b\u30de\u30c3\u30c1\u3057\u3066\u3044\u305f\u76f8\u624b\u304c\u30c0\u30df\u30fc\u3067\u306a\u3051\u308c\u3070\u3001\u30de\u30c3\u30c1\u30f3\u30b0\u3092\u89e3\u9664\u3059\u308b\n",
      "                    if matched != host_unmatched_mark:\n",
      "                         applicant_matchings[matched] = applicant_unmatched_mark\n",
      "                         stack.append(matched)\n",
      "\n",
      "                    next_start[applicant] = index\n",
      "                    break\n",
      "\n",
      "     return applicant_matchings, host_matchings\n",
      "                \n",
      "\n",
      "# \u9078\u597d\u8868\u3092\u30e9\u30f3\u30c0\u30e0\u306b\u4f5c\u308b\n",
      "def random_preference_table(row, col, **kwargs):\n",
      "     unmatch = kwargs.get('unmatch', True)\n",
      "     numpy = kwargs.get('numpy', False)\n",
      "\n",
      "     if numpy:\n",
      "          li = np.tile(np.arange(col+1, dtype=int), (row, 1))\n",
      "          stop = None if unmatch else -1\n",
      "          for i in li:\n",
      "               np.random.shuffle(i[:stop])\n",
      "          \n",
      "          return li\n",
      "\n",
      "     else:     \n",
      "          def __sshuffle(li):\n",
      "               shuffle(li)\n",
      "               return li\n",
      "\n",
      "          if unmatch:\n",
      "               return [__sshuffle(list(range(col+1))) for i in range(row)]\n",
      "          else:\n",
      "               return [__sshuffle(list(range(col))) + [col+1] for i in range(row)]\n",
      "\n",
      "\n",
      "# \u5de8\u5927\u306a\u9078\u597d\u8868\u3092\u304d\u3061\u3093\u3068\u30e9\u30f3\u30c0\u30e0\u306b\u4f5c\u308b\u306e\u306f\u5927\u5909\u6642\u9593\u304c\u304b\u304b\u308b\n",
      "# \u305d\u3053\u3067\u3001\u9078\u597d\u306e\u30d1\u30bf\u30fc\u30f3\u3092n\u500b\u7528\u610f\u3057\u3001\u305d\u306e\u4e2d\u304b\u3089\u9078\u3076\u3088\u3046\u306b\u3059\u308b\n",
      "def pseudo_random_preference_table(row, col, n=1000, **kwargs):\n",
      "     unmatch = kwargs.get('unmatch', True)\n",
      "\n",
      "     if n > row:\n",
      "          n = row\n",
      "\n",
      "     size = col+1 if unmatch else col\n",
      "     sample = np.tile(np.arange(size, dtype=int), (n, 1))\n",
      "     for i in sample:\n",
      "          np.random.shuffle(i)\n",
      "\n",
      "     index = np.random.randint(0, n, row)\n",
      "     li = np.empty((row, size))\n",
      "     li += sample[index]\n",
      "\n",
      "     return li"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      " app_table = [[3, 1, 0, 4, 2], [3, 4, 2, 0, 1]]\n",
      " hos_table = [[2, 0, 1], [0, 1, 2], [0, 2, 1], [0, 2, 1]]\n",
      "\n",
      " print(\"DA\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0 \u30b9\u30bf\u30fc\u30c8!\")\n",
      " start = time.time()\n",
      " matching = gale_shapley(app_table, hos_table)\n",
      " stop = time.time() - start\n",
      " print(\"\u30b9\u30c8\u30c3\u30d7\uff01\")\n",
      " print(\"\u5b9f\u884c\u6642\u9593\u306f \" + str(stop) + \" \u79d2\u3067\u3057\u305f\\n\")\n",
      "\n",
      " print(\"\u7533\u3057\u8fbc\u307f\u5074\u304b\u3089\u307f\u305f\u30de\u30c3\u30c1\u30f3\u30b0\u306f\")\n",
      " print(matching[0])\n",
      " print(\"\u53d7\u3051\u5165\u308c\u5074\u304b\u3089\u307f\u305f\u30de\u30c3\u30c1\u30f3\u30b0\u306f\")\n",
      " print(matching[1])\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "DA\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0 \u30b9\u30bf\u30fc\u30c8!\n",
        "\u30b9\u30c8\u30c3\u30d7\uff01\n",
        "\u5b9f\u884c\u6642\u9593\u306f 0.000275135040283 \u79d2\u3067\u3057\u305f\n",
        "\n",
        "\u7533\u3057\u8fbc\u307f\u5074\u304b\u3089\u307f\u305f\u30de\u30c3\u30c1\u30f3\u30b0\u306f\n",
        "[3 4]\n",
        "\u53d7\u3051\u5165\u308c\u5074\u304b\u3089\u307f\u305f\u30de\u30c3\u30c1\u30f3\u30b0\u306f\n",
        "[2 2 2 0]\n"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      " app_table = [[0, 2, 1, 3], [2, 1, 3, 0], [3, 1, 0, 2]]\n",
      " hos_table = [[3, 0, 2, 1], [2, 0, 1, 3], [2, 0, 3, 1]]\n",
      "\n",
      " print(\"DA\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0 \u30b9\u30bf\u30fc\u30c8!\")\n",
      " start = time.time()\n",
      " matching = gale_shapley(app_table, hos_table)\n",
      " stop = time.time() - start\n",
      " print(\"\u30b9\u30c8\u30c3\u30d7\uff01\")\n",
      " print(\"\u5b9f\u884c\u6642\u9593\u306f \" + str(stop) + \" \u79d2\u3067\u3057\u305f\\n\")\n",
      "\n",
      " print(\"\u7533\u3057\u8fbc\u307f\u5074\u304b\u3089\u307f\u305f\u30de\u30c3\u30c1\u30f3\u30b0\u306f\")\n",
      " print(matching[0])\n",
      " print(\"\u53d7\u3051\u5165\u308c\u5074\u304b\u3089\u307f\u305f\u30de\u30c3\u30c1\u30f3\u30b0\u306f\")\n",
      " print(matching[1])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "DA\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0 \u30b9\u30bf\u30fc\u30c8!\n",
        "\u30b9\u30c8\u30c3\u30d7\uff01\n",
        "\u5b9f\u884c\u6642\u9593\u306f 0.000240802764893 \u79d2\u3067\u3057\u305f\n",
        "\n",
        "\u7533\u3057\u8fbc\u307f\u5074\u304b\u3089\u307f\u305f\u30de\u30c3\u30c1\u30f3\u30b0\u306f\n",
        "[2 1 3]\n",
        "\u53d7\u3051\u5165\u308c\u5074\u304b\u3089\u307f\u305f\u30de\u30c3\u30c1\u30f3\u30b0\u306f\n",
        "[3 1 0]\n"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      " start = time.time()\n",
      " app_table = random_preference_table(1000, 1000)\n",
      " hos_table = random_preference_table(1000, 1000)\n",
      " stop = time.time() - start\n",
      " print(\"\u9078\u597d\u8868\u751f\u6210\u306f \" + str(stop) + \" \u79d2\u3067\u3057\u305f\\n\")\n",
      "\n",
      " print(\"DA\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0 \u30b9\u30bf\u30fc\u30c8!\")\n",
      " start = time.time()\n",
      " matching = gale_shapley(app_table, hos_table)\n",
      " stop = time.time() - start\n",
      " print(\"\u30b9\u30c8\u30c3\u30d7\uff01\")\n",
      " print(\"\u5b9f\u884c\u6642\u9593\u306f \" + str(stop) + \" \u79d2\u3067\u3057\u305f\\n\")\n",
      "\n",
      " print(\"\u7533\u3057\u8fbc\u307f\u5074\u304b\u3089\u307f\u305f\u30de\u30c3\u30c1\u30f3\u30b0\u306f\")\n",
      " print(matching[0])\n",
      " print(\"\u53d7\u3051\u5165\u308c\u5074\u304b\u3089\u307f\u305f\u30de\u30c3\u30c1\u30f3\u30b0\u306f\")\n",
      " print(matching[1])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\u9078\u597d\u8868\u751f\u6210\u306f 0.756177902222 \u79d2\u3067\u3057\u305f\n",
        "\n",
        "DA\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0 \u30b9\u30bf\u30fc\u30c8!\n",
        "\u30b9\u30c8\u30c3\u30d7\uff01"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "\u5b9f\u884c\u6642\u9593\u306f 0.172663927078 \u79d2\u3067\u3057\u305f\n",
        "\n",
        "\u7533\u3057\u8fbc\u307f\u5074\u304b\u3089\u307f\u305f\u30de\u30c3\u30c1\u30f3\u30b0\u306f\n",
        "[ 218   83  462  889  405  879  686   13   16  277  386  467  881  918  165\n",
        "  868  195  427  738  539  563  719  620  460  373  189 1000  308  850  449\n",
        "  973  863  182  242  796  728  577  939  907  631  674  734  643  997  934\n",
        "  922  790  684  485  389  163  624  493  288  757  833  594   52  709  211\n",
        "  322  176  759  294  938  347   25 1000  166  107   34  864   47  561  683\n",
        "  647  114  931  121 1000  739  505  666  700  536  548   55  197  447  382\n",
        "  466  120  148  616  228  230  789  274  919   27  746  184  800  696  969\n",
        "  110   67  424  925  901  312  679  893  699  273  152  520  778  130  553\n",
        "  159  791  468  565  416  161  903  483  966  691  494  513  464  645  143\n",
        "  254  866  957  598   23 1000  535  541  402  383  983  245  781  224  208\n",
        "  991  559  687  601   36  252  534  661    8  765  538  329  378  735  748\n",
        "  904  160   91   97  717  628  836  533  611  749  158  344  438  690  962\n",
        "  640  396  217  651  249  747  742  837  608  142  326  555  200 1000  768\n",
        "  295  102  549  689  185  129  771    9  244  909  629  985  138  883   21\n",
        "  220  672  849  507  315   11  388  786  913  292   79  725  680  784  682\n",
        "  788  681  581  377  380  860  222  840  101  819  677  988  227   35  769\n",
        "   65  285   43  662  568  993  702  401  869  979  503  657  669  147  944\n",
        "  753  233  994  635  617  588 1000  155  421  499   59  848  971  694  758\n",
        "  794  376  264  167  940  821  174   76  880  196  297  597  372  504   44\n",
        "  750  920  477  231  429  701  117 1000  892  695  873  406  318  262  546\n",
        "  721  729  333  452  984  250  764  261  964  173   74  761  475  970  558\n",
        "  882  602  936  170  487  693  512  762  670  827  272 1000  692  179  360\n",
        " 1000  990  832   86  783  952  437  826  871  745  933  953  963  582   32\n",
        "  817  802 1000  824  394   45  271  343  875  459  458  247  830  527  335\n",
        "  626  385  177  412  852  540  306  105  648  109  518   94   81  275  785\n",
        "  590  574  430  243  585  667   95  716  419  128  332  816  525  937   62\n",
        "  967  857  638  858  853  234  320  345   39  356  229  404  532  235   84\n",
        "  365   40  146  263  523  622  428  524  502  281  371  656  325  623  111\n",
        "  712  854  950 1000  799  514  455  287  304 1000  209  737  605  137  237\n",
        "   88  560  564   63  484  414  387  825  500  813  463  636  219  204  369\n",
        "  157  303  841  270  136  566 1000  508  461  445  877  469  703  556  704\n",
        "  118   92  755  223  989  906  675    5  910  779  625  491  961  867  413\n",
        "  257  453    4 1000  552   48  139  807  543  705   46  216  946  488  947\n",
        " 1000  399  423  562  201  911  178  171  754  100  407  820  698  612   30\n",
        "  992   72  337    2   28  884  310  902   42  987  530  150  397  810  187\n",
        "  838  327  355  255 1000  708  341  299  580  284  403  361  331  316  311\n",
        "  915  366  122    1  676  846  132  140  526   10  707  980  411   99  809\n",
        "  732  193  914  996  328  567  917  607  443  151  763  787  375  642  134\n",
        "  842  736   57  352  890  260  127  545  364  205  801 1000  434  108  960\n",
        "  367  896  519   37  812  593  354  770  965  978  236  301  498  823  929\n",
        "  359  124  492  346  688  409  290  974  815  125  609  349  203   71  238\n",
        "  576  668  439  818  595   80  547  454  887  767  426  168  145  654  646\n",
        "  637  733  226  282  835  589  374  685  898  442  126  381  876  497  451\n",
        "  715    3  340  517  630  930  872  844  658  711  336  678  289  697  259\n",
        "  317  923   31  570  619  998  395  450  639  795  751   82  172  400  578\n",
        "  599  839   70  418  283  894  240  782  351  999  448  828  572 1000   93\n",
        " 1000  154  531  480  214   58  722  834   75  175   15  897  972  600  103\n",
        "  829  727  144  470  583  417  141  714  649  342  948   87  603  506  319\n",
        "  665  186  116   24  410  516  358  314  444  891  862    6  981  495  456\n",
        "  921  194   12  584  935   69  191  571 1000  995  627  899  280  183   22\n",
        "  916  615  924  221  760  730  198  633  613  744  653  199  811  710  756\n",
        "  123  976  752  776  954  845  856  112  293  510  792  579  803  321  239\n",
        "  181  843   60  149  368  926  874  632  246  606   18  302  861  723  398\n",
        "  393  706   85  432   77    7  774  968  741  847  422  258  490   66   41\n",
        "  106   61  253  621  481  515  528  192  190  550  870  300  215  330  156\n",
        "  474   51  291  886  425   54  928  529  726   53  596  542  673   50  241\n",
        "  614   19  370  982  433  307  634 1000  586  115  977  390  113  104  522\n",
        "  471  486  440  268  164  713   26  489  660  943  278  133  353  267  650\n",
        "  949   89   73  431  305  266  955   29 1000  575  348  415  888  408  831\n",
        "  780   38  286  379  248  775  777  797  357  276  912  188  446  655  772\n",
        "  298  908  309  202  808  975  573  805  641  945  496  664  479  511  256\n",
        "  435  942   68  213  644  521  225  878  798  885  544  162  569  251  212\n",
        "  958  119  384  501  392  956  472 1000  476  855  457 1000  865    0   96\n",
        "  509  959   98  804   17  652   90  740  592   20  671  851  604  338  537\n",
        "  806  465  441   64  793  859   33  296  905  207  478  659  900   14  391\n",
        "  986  941 1000  350  766  334  554  718  169  324  210   49  932  814   56\n",
        "  323  591  473  153  551  279  135 1000  313  731]\n",
        "\u53d7\u3051\u5165\u308c\u5074\u304b\u3089\u307f\u305f\u30de\u30c3\u30c1\u30f3\u30b0\u306f\n",
        "[ 943  543  513  646  482  472  731  800  158  202  549  215  737    7  973\n",
        "  700    8  949  790  841  954  209  749  139  723   66  861   99  514  877\n",
        "  509  662  344  966   70  238  154  588  886  398  406  809  518  242  284\n",
        "  350  490   72  485  986  838  826   57  834  830   86  989  572  695  265\n",
        "  782  811  389  438  963  240  808  106  917  740  677  613  511  872  310\n",
        "  698  277  799 1000  220  620  372  671    1  404  797  333  716  435  871\n",
        "  951  167  466  689  371  381  944  168  947  553  504  233  196  704  853\n",
        "  367  810   69  583  369  105  419  772  852   76  849  722  291  465  931\n",
        "   91   78  542  765  601  609  640  576  384  200  118 1000  546  866  569\n",
        "  996  454  433  207  486  547  711  189  134  707  627  407  253   92  783\n",
        "  521  564  115  993  691  262  824  450  175  120  166  125  926   50  859\n",
        "   14   68  273  626  983  318  502  672  309  276  699   61  362  501  328\n",
        " 1000  780   32  748  101  199  721  524  896   25  818  741  817  556  736\n",
        "   16  279   87  756  761  192  499  903  612  448  579 1000  969  149  430\n",
        "  985   59  929  918  694  822  491  182    0  447  210  753  231  468  148\n",
        "  921  632  237   94  400   95  288 1000  256  395  403  595  434  614  779\n",
        "  681  839   33  378  203  146  788  356  889  184  305  928  155  812  135\n",
        "  528  914  480  806  659  575  307  298  408  272 1000  875  868  858 1000\n",
        "  453  351  325  114   97  373  894    9  865  995  747  414  633  679  534\n",
        "  241  887  427   53  657  606  827  219  773   63  195  967  280  900  532\n",
        "  821  596  791  451  428  874  366  845   27  902  516  539  110  998  727\n",
        "  214  538  660  297  719  396  778   60  990  984  417  190  526  559  161\n",
        "  823  537  385  302  980  359  655  512  958 1000  647  531  714  352  176\n",
        "  397  603   65  880  611  978  683  573  867  591  527  399  893  726  600\n",
        "  329  536 1000 1000  578  405  541  585  784  449  842  415  282   24  636\n",
        "  567  271  228  162  888  229  641   89  144  932  361   10  441  216   49\n",
        "  851  974  934  795  349  666  181  522  794  496  673  247  143  535  401\n",
        "    4  296  505  883  605  724  552  363  479  440  881  124  710  678  383\n",
        " 1000  263  805  497  107  829  625   17  411  289  377  873  798  844  582\n",
        "  915 1000  336  177  617  857  962  639  563  728  459  897   88  685   29\n",
        "  667  644  303  481  622  426  734  940  355  354   23  458    2  445  132\n",
        "  961   90   11  122  461  708  855  936  992  825  312  938  287  970  912\n",
        "  693  814 1000  127  439   48  856  319  493  862  807  476  602   52  130\n",
        "  733  910  643  597  264  443  933  413  250  283   81  718  213  457  945\n",
        "  774  913  321  131  425  815  725  648  370  587  116  920  854  409  412\n",
        "  387  548  358  816  832  520  692  402  172  156  141   84  959  160   19\n",
        "  365  142  836  488  925  577  299  621   85  197  819  994  484  119  981\n",
        "  191  463 1000  314  151  436   73  498   20  437  123  455  560  244  927\n",
        "  663  742  687  906  376  879  615   36  674  776  533  227  343  709  738\n",
        "  379  848 1000  260  635  375  991  953  590   56  619  835  281  138  675\n",
        "  703  153  316  717  957  432  789  562  188  610 1000  173  508  758  840\n",
        "  751   93  259 1000  664   22  813  410  418   51  475  360  745  170  205\n",
        "  649   39  787  757  846  258  446  630  392  668  180  908  568   42  919\n",
        "  133  629   75  368  713  869  183  950  760  628  898  416  251  653  971\n",
        "  863  157  243 1000  911  720   82  380  616  252  323  955  211  837   40\n",
        "  471  544  235  656  111  222  226  224   74   47  637    6  152  604  198\n",
        "  178  129  327  320  268  294  103  658  507  113   83  290  246  462  464\n",
        "  489  796  550  530   58  763  654  420  860  712  645  382  169  982   21\n",
        " 1000  300  696  793 1000  221  833  706   35  301  755  999  555  631   41\n",
        "  163  571  431   18   80  952  803  186 1000  759  339  100  185  164  174\n",
        "  285  670  767  255  503  467  764   54  269   62  754  311  322  565  306\n",
        "  159  979  624  194  239  592  201  899 1000  801  890  768  891  117  474\n",
        "  885  147  682  334  223  374  217  566  225   96   46  121  775  964  270\n",
        "  669   34  892  923  424  102  580  346  777  948  907  960  487  904  554\n",
        "  523  762  589  444  988  608  386  345  618  234  506  275 1000  598  348\n",
        "  442  337  324  686  705  357  884  332   55  697  634  171  187  525  676\n",
        "  232  452  570  781  652  770  545  804  266  212   28  956  364  394  421\n",
        "  939  771  391  393  965  230  792  730   31   71  942  136  478   15  248\n",
        "  820  338  651  295  786  353  642  460  922    5  278   12  315  208  515\n",
        "  924  828  623  882    3  574  729  293  112  680 1000  586  701  638  746\n",
        "  972  109  517  126  165  968  470   38  901  204  473  500  895  218  557\n",
        "  540  750  561   13   98  286  735   45  661  752  108  785 1000  831  599\n",
        "  650   77  987  340   44  739  317  388   64   37  274  976  916  864  254\n",
        "  909  492  494  715  870  422 1000  335  341  769  876  935  137  930  946\n",
        "  584  477  179  342  308  593  128  390  802  104  313  267  702   30  607\n",
        "  905  766  850  594  249  551  732  843  145  304  206  975  519  236  469\n",
        "  331  150  510  245  257  744  558   43  665  684]\n"
       ]
      }
     ],
     "prompt_number": 29
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}