#!/usr/bin/env python
# coding: utf-8

# ## 問題：

# In[ ]:


a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 3

rotate(a, n)  # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
# ↑コレ


# ↑このような関数 rotate（＝配列（リスト）a の内容を n だけずらす関数）を書いてください

# ### 解答例1

# In[1]:


def rotate(a, n):
    for b in range(n):
        a.append(a.pop(0))
    return a


# In[2]:


a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 3

rotate(a, n)  # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
# ↑コレ


# 解説：
# 
# + 先頭を `pop` して最後尾に `append` 、を `n`回繰り返すコード。
# + 新しいリストではなく、引数に渡したリスト（オブジェクト）の内容を変更する例。
#     + ↑ただしインプレースではない（オブジェクトとしては同一で中身が変化している）
# + パフォーマンスは？
#     + 決して良くない（特に `a.pop(0)` が）

# ### 解答例2

# In[3]:


def rotate(a, n):
    return a[n:] + a[:n]


# In[4]:


a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 3

rotate(a, n)  # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
# ↑コレ


# 解説：
# 
# + リストの`n`番目以降・`n`番目より前をそれぞれスライスして、それを連結するコード。
# + 結果は新しいリストとなる（引数 `a` は変更されない）。
# + パフォーマンスは？

# ### 解答例3

# In[5]:


def rotate(a, n):
    b = list(a)
    l = len(a)
    for i in range(l):
        if i < n:
            b[i] = a[i + n]
        else:
            b[i] = a[i + n - l]
    return b


# In[6]:


a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 3

rotate(a, n)  # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
# ↑コレ


# 解説：
# 
# + 同じ長さのリストを用意して、そこにターゲットとなる要素を順に入れて行くコード。
# + 考え方（アルゴリズム）はシンプル。Python に限らず他言語でも同様に実装可能。
# + パフォーマンスは？
#     + 4行目・8行目の `l` を `len(a)` とする↓と、（特に後者は）毎回リストの長さを計算するのでよろしくない。

# In[ ]:


# よろしくない例
def rotate(a, n):
    b = list(a)
    for i in range(len(a)):
        if i < n:
            b[i] = a[i + n]
        else:
            b[i] = a[i + n - len(a)]
    return b


# ### 解答例3 別解1

# In[7]:


def rotate(a, n):
    b = list(a)
    l = len(a)
    for i in range(len(a)):
        b[i] = a[(i + n) % l]
    return b


# In[8]:


a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 3

rotate(a, n)  # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
# ↑コレ


# 解説：
# 
# + 考え方は「解答例3」そのまま。
# + `if`〜`else`で分岐する代わりに、剰余演算を利用
# + パフォーマンスは？
#     + たぶん `if`〜`else` よりはパフォーマンス向上

# ### 解答例3 別解2

# In[9]:


def rotate(a, n):
    l = len(a)
    return [a[(i + n) % l] for i in range(l)]


# In[10]:


a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 3

rotate(a, n)  # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
# ↑コレ


# 解説：
# 
# + 考え方は「解答例3」および「解答例3 別解1」そのまま。
# + Python の「リスト内包表記（List Comprehension）」を利用。
# + パフォーマンスは？
#     + 「別解2」よりさらに少し向上（してるはず）

# ### 解答例4

# In[11]:


def rotate(a, n):
    l = len(a)
    s = 0
    while n:
        g = l - n
        for i in range(s, g):
            # a[i], a[i+n] = a[i+n], a[i]
            t = a[i]
            a[i] = a[i + n]
            a[i + n] = t
        n = (s - g) % n
        s = g
    return a    


# In[12]:


a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 3

rotate(a, n)  # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
# ↑コレ


# 解説：
# 
# + インプレース（＝新しいリストを作らず、要素を入れ替えるだけ）のコード例。
# + 見た目少し煩雑だが、リストの長さ `l` に対して最大でも `l-1`回 の スワップ で完了。
# + パフォーマンスは？
#     + 8〜10行目のスワップ（要素入替）処理を、7行目のように1行で書いてしまうと、パフォーマンスが落ちしてしまう。

# ### 解答例5（追加）

# In[13]:


def rotate(a, n):
    from fractions import gcd
    l = len(a)
    g = gcd(l, n)
    for s in range(g):
        t = a[s]
        for i in range(1, l / g):
            a[(s + (i - 1) * n) % l] = a[(s + i * n) % l]
        a[(s - n) % l] = t
    return a    


# In[14]:


a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 3

rotate(a, n)  # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
# ↑コレ


# 解説：
# 
# + インプレース（＝新しいリストを作らず、要素を入れ替えるだけ）のコード例。
# + 解答例4 で２つずつスワップしていたのを、`l/gcd(l,n)`個 ずつの入替（巡回置換）に差し替えた例。
# + パフォーマンスは？
#     + 《未検証》

# ### 参考：

# In[15]:


from collections import deque

d = deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
d


# In[16]:


d.rotate(-3)
d


# 解説：
# 
# + リストではない（配列でもない）が、`deque`（双方向キュー）を利用した`rotate`の例。
# + 引数の解釈が異なるため、題意の仕様を満たすにはマイナスの値を指定する必要あり。
# + パフォーマンスは？
#     + 内部でやっていることは「解答例1」相当、ただし普通のリストよりは（`pop(0)` 相当の処理も）パフォーマンスは良い。

# In[ ]: