derange_sample.jl

derange_sample.jl.ipynb

derange_sample.py.ipynb

{
  "cells": [
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T23:22:52.087085",
          "end_time": "2017-08-25T23:22:52.224482"
        },
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "import numpy as np",
      "execution_count": 1,
      "outputs": []
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T23:22:53.063268",
          "end_time": "2017-08-25T23:22:53.088568"
        },
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "def derange(items):\n    perm = np.array(items) # clone to np.ndarray\n    n = len(perm)\n    if n < 2:\n        return np.array([])\n    if n == 2:\n        return np.array([perm[1], perm[0]])\n    montmort = [0] * (n + 1)\n    montmort[2] = 1\n    montmort[3] = 2\n    for i in range(4, n + 1):\n        montmort[i] = (i - 1) * (montmort[i-1] + montmort[i-2])\n    n -= 1\n    i = np.random.randint(n)\n    perm[n], perm[i] = perm[i], perm[n]\n    idxs = np.arange(n)\n    while n > 2:\n        k = int(np.random.rand() * (montmort[n] + montmort[n-1]))\n        if k >= montmort[n]:\n            idxs = np.hstack([idxs[:i], idxs[i+1:]])\n            #        ^- same as `np.delete(idxs, i)` (much faster)\n            n -= 2\n        else:\n            n -= 1\n        i = k % n\n        perm[idxs[n]], perm[idxs[i]] = perm[idxs[i]], perm[idxs[n]]\n    if n == 2:\n        perm[idxs[1]], perm[idxs[0]] = perm[idxs[0]], perm[idxs[1]]\n    return perm",
      "execution_count": 2,
      "outputs": []
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T23:22:54.074603",
          "end_time": "2017-08-25T23:22:54.081499"
        },
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "# original: http://qiita.com/HigashinoSola/items/47f2355604c2650f44b7\ndef count_derange(items, n, derange=derange):\n    counter = {}\n    for _ in range(n):\n        p = tuple(derange(items))\n        if p in counter:\n            counter[p] += 1\n        else:\n            counter[p] = 1\n    return counter",
      "execution_count": 3,
      "outputs": []
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T23:22:56.252901",
          "end_time": "2017-08-25T23:22:58.192206"
        },
        "trusted": true,
        "collapsed": false,
        "scrolled": false
      },
      "cell_type": "code",
      "source": "%time count_derange(list('abcd'), 100000)",
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "text": "CPU times: user 1.8 s, sys: 33 ms, total: 1.83 s\nWall time: 1.92 s\n",
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "{('b', 'a', 'd', 'c'): 11091,\n ('b', 'c', 'd', 'a'): 10923,\n ('b', 'd', 'a', 'c'): 11091,\n ('c', 'a', 'd', 'b'): 11050,\n ('c', 'd', 'a', 'b'): 11284,\n ('c', 'd', 'b', 'a'): 11208,\n ('d', 'a', 'b', 'c'): 11299,\n ('d', 'c', 'a', 'b'): 11031,\n ('d', 'c', 'b', 'a'): 11023}"
          },
          "metadata": {},
          "execution_count": 4
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T23:22:59.684545",
          "end_time": "2017-08-25T23:23:01.970071"
        },
        "trusted": true,
        "collapsed": false,
        "scrolled": false
      },
      "cell_type": "code",
      "source": "%time count_derange(list('abcde'), 100000)",
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "text": "CPU times: user 2.12 s, sys: 24.9 ms, total: 2.15 s\nWall time: 2.28 s\n",
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "{('b', 'a', 'd', 'e', 'c'): 2205,\n ('b', 'a', 'e', 'c', 'd'): 2314,\n ('b', 'c', 'a', 'e', 'd'): 2257,\n ('b', 'c', 'd', 'e', 'a'): 2307,\n ('b', 'c', 'e', 'a', 'd'): 2277,\n ('b', 'd', 'a', 'e', 'c'): 2308,\n ('b', 'd', 'e', 'a', 'c'): 2323,\n ('b', 'd', 'e', 'c', 'a'): 2231,\n ('b', 'e', 'a', 'c', 'd'): 2223,\n ('b', 'e', 'd', 'a', 'c'): 2247,\n ('b', 'e', 'd', 'c', 'a'): 2268,\n ('c', 'a', 'b', 'e', 'd'): 2264,\n ('c', 'a', 'd', 'e', 'b'): 2305,\n ('c', 'a', 'e', 'b', 'd'): 2283,\n ('c', 'd', 'a', 'e', 'b'): 2266,\n ('c', 'd', 'b', 'e', 'a'): 2285,\n ('c', 'd', 'e', 'a', 'b'): 2225,\n ('c', 'd', 'e', 'b', 'a'): 2236,\n ('c', 'e', 'a', 'b', 'd'): 2310,\n ('c', 'e', 'b', 'a', 'd'): 2316,\n ('c', 'e', 'd', 'a', 'b'): 2291,\n ('c', 'e', 'd', 'b', 'a'): 2325,\n ('d', 'a', 'b', 'e', 'c'): 2155,\n ('d', 'a', 'e', 'b', 'c'): 2249,\n ('d', 'a', 'e', 'c', 'b'): 2298,\n ('d', 'c', 'a', 'e', 'b'): 2334,\n ('d', 'c', 'b', 'e', 'a'): 2238,\n ('d', 'c', 'e', 'a', 'b'): 2331,\n ('d', 'c', 'e', 'b', 'a'): 2296,\n ('d', 'e', 'a', 'b', 'c'): 2282,\n ('d', 'e', 'a', 'c', 'b'): 2177,\n ('d', 'e', 'b', 'a', 'c'): 2227,\n ('d', 'e', 'b', 'c', 'a'): 2276,\n ('e', 'a', 'b', 'c', 'd'): 2330,\n ('e', 'a', 'd', 'b', 'c'): 2268,\n ('e', 'a', 'd', 'c', 'b'): 2265,\n ('e', 'c', 'a', 'b', 'd'): 2244,\n ('e', 'c', 'b', 'a', 'd'): 2215,\n ('e', 'c', 'd', 'a', 'b'): 2286,\n ('e', 'c', 'd', 'b', 'a'): 2299,\n ('e', 'd', 'a', 'b', 'c'): 2285,\n ('e', 'd', 'a', 'c', 'b'): 2279,\n ('e', 'd', 'b', 'a', 'c'): 2313,\n ('e', 'd', 'b', 'c', 'a'): 2287}"
          },
          "metadata": {},
          "execution_count": 5
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T23:23:03.220115",
          "end_time": "2017-08-25T23:23:03.524317"
        },
        "trusted": true,
        "collapsed": false
      },
      "cell_type": "code",
      "source": "%%time\nfor _ in range(1000):\n    derange(list(range(100)))",
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "text": "CPU times: user 275 ms, sys: 7.83 ms, total: 283 ms\nWall time: 301 ms\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T23:23:05.548099",
          "end_time": "2017-08-25T23:23:05.553050"
        },
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "# original: http://qiita.com/HigashinoSola/items/47f2355604c2650f44b7\ndef derange_repshf(items):\n    if not isinstance(items, np.ndarray):\n        items = np.array(items)\n    index = np.arange(items.size)\n    rand_index = index.copy()\n    while 0 in index - rand_index: #0を含んでいれば完全順列でない\n        np.random.shuffle(rand_index)\n    return items[rand_index]",
      "execution_count": 7,
      "outputs": []
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T23:23:06.911527",
          "end_time": "2017-08-25T23:23:10.952519"
        },
        "trusted": true,
        "collapsed": false
      },
      "cell_type": "code",
      "source": "%time count_derange(list('abcd'), 100000, derange=derange_repshf)",
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "text": "CPU times: user 3.93 s, sys: 35.7 ms, total: 3.96 s\nWall time: 4.04 s\n",
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "{('b', 'a', 'd', 'c'): 11090,\n ('b', 'c', 'd', 'a'): 10981,\n ('b', 'd', 'a', 'c'): 11030,\n ('c', 'a', 'd', 'b'): 11030,\n ('c', 'd', 'a', 'b'): 11121,\n ('c', 'd', 'b', 'a'): 11037,\n ('d', 'a', 'b', 'c'): 11313,\n ('d', 'c', 'a', 'b'): 11220,\n ('d', 'c', 'b', 'a'): 11178}"
          },
          "metadata": {},
          "execution_count": 8
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T23:23:12.775274",
          "end_time": "2017-08-25T23:23:17.003918"
        },
        "trusted": true,
        "collapsed": false
      },
      "cell_type": "code",
      "source": "%time count_derange(list('abcde'), 100000, derange=derange_repshf)",
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "text": "CPU times: user 4.05 s, sys: 37.4 ms, total: 4.08 s\nWall time: 4.22 s\n",
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "{('b', 'a', 'd', 'e', 'c'): 2319,\n ('b', 'a', 'e', 'c', 'd'): 2297,\n ('b', 'c', 'a', 'e', 'd'): 2293,\n ('b', 'c', 'd', 'e', 'a'): 2209,\n ('b', 'c', 'e', 'a', 'd'): 2266,\n ('b', 'd', 'a', 'e', 'c'): 2255,\n ('b', 'd', 'e', 'a', 'c'): 2266,\n ('b', 'd', 'e', 'c', 'a'): 2354,\n ('b', 'e', 'a', 'c', 'd'): 2250,\n ('b', 'e', 'd', 'a', 'c'): 2251,\n ('b', 'e', 'd', 'c', 'a'): 2309,\n ('c', 'a', 'b', 'e', 'd'): 2159,\n ('c', 'a', 'd', 'e', 'b'): 2205,\n ('c', 'a', 'e', 'b', 'd'): 2327,\n ('c', 'd', 'a', 'e', 'b'): 2329,\n ('c', 'd', 'b', 'e', 'a'): 2332,\n ('c', 'd', 'e', 'a', 'b'): 2190,\n ('c', 'd', 'e', 'b', 'a'): 2288,\n ('c', 'e', 'a', 'b', 'd'): 2220,\n ('c', 'e', 'b', 'a', 'd'): 2237,\n ('c', 'e', 'd', 'a', 'b'): 2256,\n ('c', 'e', 'd', 'b', 'a'): 2302,\n ('d', 'a', 'b', 'e', 'c'): 2309,\n ('d', 'a', 'e', 'b', 'c'): 2263,\n ('d', 'a', 'e', 'c', 'b'): 2251,\n ('d', 'c', 'a', 'e', 'b'): 2273,\n ('d', 'c', 'b', 'e', 'a'): 2227,\n ('d', 'c', 'e', 'a', 'b'): 2279,\n ('d', 'c', 'e', 'b', 'a'): 2235,\n ('d', 'e', 'a', 'b', 'c'): 2218,\n ('d', 'e', 'a', 'c', 'b'): 2219,\n ('d', 'e', 'b', 'a', 'c'): 2269,\n ('d', 'e', 'b', 'c', 'a'): 2262,\n ('e', 'a', 'b', 'c', 'd'): 2350,\n ('e', 'a', 'd', 'b', 'c'): 2275,\n ('e', 'a', 'd', 'c', 'b'): 2295,\n ('e', 'c', 'a', 'b', 'd'): 2341,\n ('e', 'c', 'b', 'a', 'd'): 2268,\n ('e', 'c', 'd', 'a', 'b'): 2249,\n ('e', 'c', 'd', 'b', 'a'): 2308,\n ('e', 'd', 'a', 'b', 'c'): 2298,\n ('e', 'd', 'a', 'c', 'b'): 2356,\n ('e', 'd', 'b', 'a', 'c'): 2247,\n ('e', 'd', 'b', 'c', 'a'): 2294}"
          },
          "metadata": {},
          "execution_count": 9
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T23:23:21.990892",
          "end_time": "2017-08-25T23:23:22.077989"
        },
        "trusted": true,
        "collapsed": false
      },
      "cell_type": "code",
      "source": "%%time\nfor _ in range(1000):\n    derange_repshf(list(range(100)))",
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "text": "CPU times: user 74 ms, sys: 6.92 ms, total: 80.9 ms\nWall time: 81.9 ms\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T23:23:30.877961",
          "end_time": "2017-08-25T23:23:30.888641"
        },
        "trusted": true,
        "collapsed": false
      },
      "cell_type": "code",
      "source": "# original: http://qiita.com/ttatsf/items/d4543ccc80e0fbe3891d#comment-3eccf9c112d73c505bc2\ndef derange_ttatsf(items):\n    if not isinstance(items, np.ndarray):\n        items = np.array(items)\n    length = len(items)\n    ref = np.arange(length)\n    np.random.shuffle(ref)\n    xs = np.array(ref)\n    for i in range(length - 2):\n        if xs[i] == ref[i]:\n            j = np.random.randint(i + 1, length)\n        else:\n            j = np.random.randint(i, length)\n        xs[i] , xs[j] = xs[j], xs[i] \n    if xs[-2] == ref[-2] or xs[-1] == ref[-1] or np.random.randint(2):\n        xs[-2], xs[-1] = xs[-1], xs[-2]\n    move_dict = dict(zip(ref, xs))\n    return np.array([items[move_dict[i]] for i in range(length)])",
      "execution_count": 11,
      "outputs": []
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T23:23:32.180070",
          "end_time": "2017-08-25T23:23:35.742809"
        },
        "trusted": true,
        "collapsed": false,
        "scrolled": true
      },
      "cell_type": "code",
      "source": "%time count_derange(list('abcd'), 100000, derange=derange_ttatsf)",
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "stream",
          "text": "CPU times: user 3.47 s, sys: 45.5 ms, total: 3.51 s\nWall time: 3.56 s\n",
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "{('b', 'a', 'd', 'c'): 9282,\n ('b', 'c', 'd', 'a'): 11908,\n ('b', 'd', 'a', 'c'): 12150,\n ('c', 'a', 'd', 'b'): 12027,\n ('c', 'd', 'a', 'b'): 9294,\n ('c', 'd', 'b', 'a'): 11944,\n ('d', 'a', 'b', 'c'): 12024,\n ('d', 'c', 'a', 'b'): 12047,\n ('d', 'c', 'b', 'a'): 9324}"
          },
          "metadata": {},
          "execution_count": 12
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T23:23:36.990172",
          "end_time": "2017-08-25T23:23:37.317501"
        },
        "trusted": true,
        "collapsed": false
      },
      "cell_type": "code",
      "source": "%%time\nfor _ in range(1000):\n    derange_ttatsf(list(range(100)))",
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "stream",
          "text": "CPU times: user 310 ms, sys: 7.98 ms, total: 318 ms\nWall time: 324 ms\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "",
      "execution_count": null,
      "outputs": []
    }
  ],
  "metadata": {
    "kernelspec": {
      "name": "python3",
      "display_name": "IPython (Python 3)",
      "language": "python"
    },
    "latex_envs": {
      "eqNumInitial": 1,
      "eqLabelWithNumbers": true,
      "current_citInitial": 1,
      "cite_by": "apalike",
      "bibliofile": "biblio.bib",
      "LaTeX_envs_menu_present": true,
      "labels_anchors": false,
      "latex_user_defs": false,
      "user_envs_cfg": false,
      "report_style_numbering": false,
      "autocomplete": true,
      "hotkeys": {
        "equation": "Ctrl-E",
        "itemize": "Ctrl-I"
      }
    },
    "language_info": {
      "mimetype": "text/x-python",
      "nbconvert_exporter": "python",
      "name": "python",
      "pygments_lexer": "ipython3",
      "version": "3.4.3",
      "file_extension": ".py",
      "codemirror_mode": {
        "version": 3,
        "name": "ipython"
      }
    },
    "gist": {
      "id": "cc111b1ce6d36cccc1b37448639eb155",
      "data": {
        "description": "derange_sample.py",
        "public": true
      }
    },
    "_draft": {
      "nbviewer_url": "https://gist.github.com/cc111b1ce6d36cccc1b37448639eb155"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}