derange_sample.jl

derange_sample.jl.ipynb

{
  "cells": [
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T14:24:47.338Z",
          "end_time": "2017-08-25T23:24:48.263000"
        },
        "trusted": true,
        "collapsed": false
      },
      "cell_type": "code",
      "source": "function randint(rng::Range{BigInt})::BigInt\n    l = first(rng)\n    m = last(rng)\n    typemin(Int) <= l <= m <= typemax(Int) && return rand(Int(l):Int(m))\n    floor(BigInt, rand() * (m - l + 1)) + l\nend\n\nrandint(rng::Range{<:Integer}) = rand(rng)",
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "randint (generic function with 2 methods)"
          },
          "metadata": {},
          "execution_count": 1
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T14:24:50.077Z",
          "end_time": "2017-08-25T23:24:50.134000"
        },
        "trusted": true,
        "collapsed": false
      },
      "cell_type": "code",
      "source": "function derange(arr::AbstractVector{<:Any})\n    n = length(arr)\n    n < 2 && return []\n    n == 2 && return [arr[2], arr[1]]\n    montmort = zeros(BigInt, n)\n    montmort[2] = big\"1\"\n    montmort[3] = big\"2\"\n    for i = 4:n\n        montmort[i] = (i - 1) * (montmort[i-1] + montmort[i-2])\n    end\n    perm = [arr;] # clone to concrete Vector\n    i = randint(1:n-1)\n    perm[n], perm[i] = perm[i], perm[n]\n    n -= 1\n    idxs = 1:n\n    while n > 2\n        k = randint(1:montmort[n-1]+montmort[n])\n        if k > montmort[n]\n            idxs = [idxs[1:i-1];idxs[i+1:n]]\n            n -= 1\n        end\n        i = Int(mod1(k, n-1))\n        perm[idxs[n]], perm[idxs[i]] = perm[idxs[i]], perm[idxs[n]]\n        n -= 1\n    end\n    if n == 2\n        perm[idxs[2]], perm[idxs[1]] = perm[idxs[1]], perm[idxs[2]]\n    end\n    perm\nend",
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "derange (generic function with 1 method)"
          },
          "metadata": {},
          "execution_count": 2
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T14:24:52.208Z",
          "end_time": "2017-08-25T23:24:52.216000"
        },
        "trusted": true,
        "collapsed": false
      },
      "cell_type": "code",
      "source": "function count_derange(arr::AbstractVector, n::Int; derange::Function=current_module().derange)\n    N = length(arr)\n    counter = Dict{NTuple{N,eltype(arr)}, Int}()\n    for _ = 1:n\n        p = tuple(derange(arr)...)\n        if haskey(counter, p)\n            counter[p] += 1\n        else\n            counter[p] = 1\n        end\n    end\n    counter\nend",
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "count_derange (generic function with 1 method)"
          },
          "metadata": {},
          "execution_count": 3
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T14:24:57.994Z",
          "end_time": "2017-08-25T23:24:58.484000"
        },
        "trusted": true,
        "collapsed": false
      },
      "cell_type": "code",
      "source": "@time count_derange(collect(\"abcd\"), 100000)",
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "text": "  0.486807 seconds (5.76 M allocations: 151.939 MiB, 29.60% gc time)\n",
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "Dict{NTuple{4,Char},Int64} with 9 entries:\n  ('c', 'd', 'b', 'a') => 11366\n  ('d', 'c', 'a', 'b') => 11203\n  ('d', 'c', 'b', 'a') => 10937\n  ('b', 'a', 'd', 'c') => 11236\n  ('c', 'd', 'a', 'b') => 11103\n  ('d', 'a', 'b', 'c') => 11010\n  ('c', 'a', 'd', 'b') => 11220\n  ('b', 'd', 'a', 'c') => 10852\n  ('b', 'c', 'd', 'a') => 11073"
          },
          "metadata": {},
          "execution_count": 5
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T14:25:29.624Z",
          "end_time": "2017-08-25T23:25:30.467000"
        },
        "trusted": true,
        "collapsed": false
      },
      "cell_type": "code",
      "source": "@time count_derange(collect(\"abcde\"), 100000)",
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "text": "  0.837095 seconds (9.44 M allocations: 241.891 MiB, 34.22% gc time)\n",
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "Dict{NTuple{5,Char},Int64} with 44 entries:\n  ('b', 'd', 'a', 'e', 'c') => 2231\n  ('e', 'c', 'd', 'a', 'b') => 2236\n  ('b', 'e', 'd', 'a', 'c') => 2368\n  ('d', 'c', 'e', 'b', 'a') => 2361\n  ('c', 'a', 'b', 'e', 'd') => 2195\n  ('e', 'd', 'a', 'c', 'b') => 2200\n  ('d', 'e', 'b', 'c', 'a') => 2318\n  ('d', 'c', 'e', 'a', 'b') => 2293\n  ('c', 'd', 'e', 'b', 'a') => 2207\n  ('e', 'a', 'd', 'c', 'b') => 2262\n  ('e', 'd', 'b', 'c', 'a') => 2237\n  ('d', 'a', 'e', 'b', 'c') => 2195\n  ('c', 'd', 'a', 'e', 'b') => 2260\n  ('d', 'c', 'b', 'e', 'a') => 2310\n  ('c', 'd', 'e', 'a', 'b') => 2288\n  ('d', 'a', 'e', 'c', 'b') => 2353\n  ('e', 'c', 'b', 'a', 'd') => 2242\n  ('c', 'd', 'b', 'e', 'a') => 2227\n  ('c', 'e', 'd', 'a', 'b') => 2371\n  ('c', 'a', 'e', 'b', 'd') => 2262\n  ('d', 'e', 'a', 'c', 'b') => 2317\n  ('b', 'c', 'e', 'a', 'd') => 2272\n  ('c', 'e', 'd', 'b', 'a') => 2311\n  ('b', 'a', 'e', 'c', 'd') => 2272\n  ('e', 'd', 'b', 'a', 'c') => 2279\n  ⋮                         => ⋮"
          },
          "metadata": {},
          "execution_count": 8
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T14:25:02.374Z",
          "end_time": "2017-08-25T23:25:03.111000"
        },
        "trusted": true,
        "collapsed": false
      },
      "cell_type": "code",
      "source": "@time for _=1:1000 derange([1:100;]) end",
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "text": "  0.524544 seconds (5.30 M allocations: 160.240 MiB, 32.25% gc time)\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T14:25:40.116Z",
          "end_time": "2017-08-25T23:25:40.122000"
        },
        "trusted": true,
        "collapsed": false
      },
      "cell_type": "code",
      "source": "function derange_repshf(items::AbstractVector{<:Any})\n    index = 1:length(items)\n    rand_index = [index;] # copy to a concrete array\n    while any(index .== rand_index)\n        shuffle!(rand_index)\n    end\n    return items[rand_index]\nend",
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "derange_repshf (generic function with 1 method)"
          },
          "metadata": {},
          "execution_count": 9
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T14:25:44.145Z",
          "end_time": "2017-08-25T23:25:44.995000"
        },
        "trusted": true,
        "collapsed": false
      },
      "cell_type": "code",
      "source": "@time count_derange(collect(\"abcd\"), 100000, derange=derange_repshf)",
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "stream",
          "text": "  0.844243 seconds (2.56 M allocations: 1.550 GiB, 25.04% gc time)\n",
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "Dict{NTuple{4,Char},Int64} with 9 entries:\n  ('b', 'c', 'd', 'a') => 11313\n  ('d', 'c', 'a', 'b') => 10999\n  ('c', 'd', 'a', 'b') => 10898\n  ('d', 'c', 'b', 'a') => 11112\n  ('d', 'a', 'b', 'c') => 11273\n  ('b', 'a', 'd', 'c') => 11023\n  ('c', 'a', 'd', 'b') => 10990\n  ('b', 'd', 'a', 'c') => 11076\n  ('c', 'd', 'b', 'a') => 11316"
          },
          "metadata": {},
          "execution_count": 11
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T14:26:01.164Z",
          "end_time": "2017-08-25T23:26:02.074000"
        },
        "trusted": true,
        "collapsed": false
      },
      "cell_type": "code",
      "source": "@time count_derange(collect(\"abcde\"), 100000, derange=derange_repshf)",
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "stream",
          "text": "  0.903233 seconds (2.64 M allocations: 1.577 GiB, 23.06% gc time)\n",
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "Dict{NTuple{5,Char},Int64} with 44 entries:\n  ('b', 'd', 'a', 'e', 'c') => 2269\n  ('e', 'c', 'd', 'a', 'b') => 2311\n  ('b', 'e', 'd', 'a', 'c') => 2257\n  ('d', 'c', 'e', 'b', 'a') => 2291\n  ('c', 'a', 'b', 'e', 'd') => 2373\n  ('e', 'd', 'a', 'c', 'b') => 2285\n  ('d', 'e', 'b', 'c', 'a') => 2197\n  ('d', 'c', 'e', 'a', 'b') => 2254\n  ('c', 'd', 'e', 'b', 'a') => 2276\n  ('e', 'a', 'd', 'c', 'b') => 2240\n  ('e', 'd', 'b', 'c', 'a') => 2276\n  ('d', 'a', 'e', 'b', 'c') => 2224\n  ('c', 'd', 'a', 'e', 'b') => 2328\n  ('d', 'c', 'b', 'e', 'a') => 2355\n  ('c', 'd', 'e', 'a', 'b') => 2269\n  ('e', 'c', 'b', 'a', 'd') => 2292\n  ('d', 'a', 'e', 'c', 'b') => 2339\n  ('c', 'd', 'b', 'e', 'a') => 2206\n  ('c', 'e', 'd', 'a', 'b') => 2272\n  ('c', 'a', 'e', 'b', 'd') => 2281\n  ('d', 'e', 'a', 'c', 'b') => 2276\n  ('b', 'c', 'e', 'a', 'd') => 2227\n  ('c', 'e', 'd', 'b', 'a') => 2334\n  ('b', 'a', 'e', 'c', 'd') => 2195\n  ('e', 'd', 'b', 'a', 'c') => 2270\n  ⋮                         => ⋮"
          },
          "metadata": {},
          "execution_count": 13
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2017-08-25T14:26:05.860Z",
          "end_time": "2017-08-25T23:26:05.985000"
        },
        "trusted": true,
        "collapsed": false
      },
      "cell_type": "code",
      "source": "@time for _=1:1000 derange_repshf([1:100;]) end",
      "execution_count": 14,
      "outputs": [
        {
          "output_type": "stream",
          "text": "  0.014551 seconds (20.47 k allocations: 17.932 MiB, 31.05% gc time)\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "",
      "execution_count": null,
      "outputs": []
    }
  ],
  "metadata": {
    "kernelspec": {
      "name": "julia-0.6",
      "display_name": "Julia 0.6.0",
      "language": "julia"
    },
    "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": "application/julia",
      "file_extension": ".jl",
      "version": "0.6.0",
      "name": "julia"
    },
    "gist": {
      "id": "cc111b1ce6d36cccc1b37448639eb155",
      "data": {
        "description": "derange_sample.jl",
        "public": true
      }
    },
    "_draft": {
      "nbviewer_url": "https://gist.github.com/cc111b1ce6d36cccc1b37448639eb155"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}

derange_sample.py.ipynb