{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 問題："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "n = 3\n",
    "\n",
    "rotate(a, n)  # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]\n",
    "# ↑コレ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "↑このような関数 rotate（＝配列（リスト）a の内容を n だけずらす関数）を書いてください"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 解答例1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def rotate(a, n):\n",
    "    for b in range(n):\n",
    "        a.append(a.pop(0))\n",
    "    return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 4, 5, 6, 7, 8, 9, 0, 1, 2]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "n = 3\n",
    "\n",
    "rotate(a, n)  # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]\n",
    "# ↑コレ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "解説：\n",
    "\n",
    "+ 先頭を `pop` して最後尾に `append` 、を `n`回繰り返すコード。\n",
    "+ 新しいリストではなく、引数に渡したリスト（オブジェクト）の内容を変更する例。\n",
    "    + ↑ただしインプレースではない（オブジェクトとしては同一で中身が変化している）\n",
    "+ パフォーマンスは？\n",
    "    + 決して良くない（特に `a.pop(0)` が）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 解答例2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def rotate(a, n):\n",
    "    return a[n:] + a[:n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 4, 5, 6, 7, 8, 9, 0, 1, 2]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "n = 3\n",
    "\n",
    "rotate(a, n)  # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]\n",
    "# ↑コレ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "解説：\n",
    "\n",
    "+ リストの`n`番目以降・`n`番目より前をそれぞれスライスして、それを連結するコード。\n",
    "+ 結果は新しいリストとなる（引数 `a` は変更されない）。\n",
    "+ パフォーマンスは？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 解答例3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def rotate(a, n):\n",
    "    b = list(a)\n",
    "    l = len(a)\n",
    "    for i in range(l):\n",
    "        if i < n:\n",
    "            b[i] = a[i + n]\n",
    "        else:\n",
    "            b[i] = a[i + n - l]\n",
    "    return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 4, 5, 6, 7, 8, 9, 0, 1, 2]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "n = 3\n",
    "\n",
    "rotate(a, n)  # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]\n",
    "# ↑コレ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "解説：\n",
    "\n",
    "+ 同じ長さのリストを用意して、そこにターゲットとなる要素を順に入れて行くコード。\n",
    "+ 考え方（アルゴリズム）はシンプル。Python に限らず他言語でも同様に実装可能。\n",
    "+ パフォーマンスは？\n",
    "    + 4行目・8行目の `l` を `len(a)` とする↓と、（特に後者は）毎回リストの長さを計算するのでよろしくない。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# よろしくない例\n",
    "def rotate(a, n):\n",
    "    b = list(a)\n",
    "    for i in range(len(a)):\n",
    "        if i < n:\n",
    "            b[i] = a[i + n]\n",
    "        else:\n",
    "            b[i] = a[i + n - len(a)]\n",
    "    return b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 解答例3 別解1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def rotate(a, n):\n",
    "    b = list(a)\n",
    "    l = len(a)\n",
    "    for i in range(len(a)):\n",
    "        b[i] = a[(i + n) % l]\n",
    "    return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 4, 5, 6, 7, 8, 9, 0, 1, 2]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "n = 3\n",
    "\n",
    "rotate(a, n)  # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]\n",
    "# ↑コレ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "解説：\n",
    "\n",
    "+ 考え方は「解答例3」そのまま。\n",
    "+ `if`〜`else`で分岐する代わりに、剰余演算を利用\n",
    "+ パフォーマンスは？\n",
    "    + たぶん `if`〜`else` よりはパフォーマンス向上"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 解答例3 別解2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def rotate(a, n):\n",
    "    l = len(a)\n",
    "    return [a[(i + n) % l] for i in range(l)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 4, 5, 6, 7, 8, 9, 0, 1, 2]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "n = 3\n",
    "\n",
    "rotate(a, n)  # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]\n",
    "# ↑コレ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "解説：\n",
    "\n",
    "+ 考え方は「解答例3」および「解答例3 別解1」そのまま。\n",
    "+ Python の「リスト内包表記（List Comprehension）」を利用。\n",
    "+ パフォーマンスは？\n",
    "    + 「別解2」よりさらに少し向上（してるはず）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 解答例4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def rotate(a, n):\n",
    "    l = len(a)\n",
    "    s = 0\n",
    "    while n:\n",
    "        g = l - n\n",
    "        for i in range(s, g):\n",
    "            # a[i], a[i+n] = a[i+n], a[i]\n",
    "            t = a[i]\n",
    "            a[i] = a[i + n]\n",
    "            a[i + n] = t\n",
    "        n = (s - g) % n\n",
    "        s = g\n",
    "    return a    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 4, 5, 6, 7, 8, 9, 0, 1, 2]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "n = 3\n",
    "\n",
    "rotate(a, n)  # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]\n",
    "# ↑コレ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "解説：\n",
    "\n",
    "+ インプレース（＝新しいリストを作らず、要素を入れ替えるだけ）のコード例。\n",
    "+ 見た目少し煩雑だが、リストの長さ `l` に対して最大でも `l-1`回 の スワップ で完了。\n",
    "+ パフォーマンスは？\n",
    "    + 8〜10行目のスワップ（要素入替）処理を、7行目のように1行で書いてしまうと、パフォーマンスが落ちしてしまう。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 解答例5（追加）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def rotate(a, n):\n",
    "    from fractions import gcd\n",
    "    l = len(a)\n",
    "    g = gcd(l, n)\n",
    "    for s in range(g):\n",
    "        t = a[s]\n",
    "        for i in range(1, l / g):\n",
    "            a[(s + (i - 1) * n) % l] = a[(s + i * n) % l]\n",
    "        a[(s - n) % l] = t\n",
    "    return a    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 4, 5, 6, 7, 8, 9, 0, 1, 2]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "n = 3\n",
    "\n",
    "rotate(a, n)  # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]\n",
    "# ↑コレ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "解説：\n",
    "\n",
    "+ インプレース（＝新しいリストを作らず、要素を入れ替えるだけ）のコード例。\n",
    "+ 解答例4 で２つずつスワップしていたのを、`l/gcd(l,n)`個 ずつの入替（巡回置換）に差し替えた例。\n",
    "+ パフォーマンスは？\n",
    "    + 《未検証》"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 参考："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "d = deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([3, 4, 5, 6, 7, 8, 9, 0, 1, 2])"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d.rotate(-3)\n",
    "d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "解説：\n",
    "\n",
    "+ リストではない（配列でもない）が、`deque`（双方向キュー）を利用した`rotate`の例。\n",
    "+ 引数の解釈が異なるため、題意の仕様を満たすにはマイナスの値を指定する必要あり。\n",
    "+ パフォーマンスは？\n",
    "    + 内部でやっていることは「解答例1」相当、ただし普通のリストよりは（`pop(0)` 相当の処理も）パフォーマンスは良い。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}