この記事はデータ構造とアルゴリズムAdvent Calendar 2021 12日目の記事です。
In-Shuffle問題
この記事ではカードをin-shuffleすることを考えます。in-shuffleとはカードの山を半分の地点で、2つの山にわけ、それらの山のカードを交互に入れ込みカードをシャッフルする方法です。マジシャンがよくやるアレですね。
アルゴリズム的に書くと次のようになります。
| In-Shuffle問題 |
|---|
| サイズ$2n$の配列$A[1..2n]$が与えられたとき、この配列$A$を$A'[2i \text{ mod }(2n+1)]=A[i]$となる配列$A'$へ変換する |
例で見てみましょう。
$A=(1, 2, 3, 4, 5, 6)$のとき、この配列を$(1, 2, 3), (4, 5, 6)$の2つの山へ分け、先頭から順番に要素を取り出し１つの山$A'=(4, 1, 5, 2, 6, 3)$へ並べ替えます。
$A[i]$が数式どおり$2i \mod (2n+1)$の位置に移動しているかをチェックしましょう。
$1, 2, 3, 4, 5, 6$はそれぞれ$2, 4, 6, 1, 3, 5$の位置へ移動しており、$A'[2i \mod (2n+1)]=A[i]$はin-shuffleを正しく表しているようですね。
$A$のin-shuffleを計算する方法を考えることにしましょう。
入力$A$に加えてもう１つサイズ$2n$の配列があれば、$A$の移動先をその配列に定義どおりにコピーし、すべてコピーし終わった後に全体を$A$にコピーすれば計算できます。簡単ですね。
問題を解くこと自体は簡単ということが分かったので、更に発展してアルゴリズム的にもう少し頑張って解くことを考えてみましょう。アルゴリズム的には時間は速ければ速い方が、領域は少なければ少ないほうが良いです。この記事では線形時間で領域をほぼ使わず、つまり配列$A$と定数領域のみを使って計算する、in-placeにin-shuffleするアルゴリズムを考えます。
紹介するアルゴリズムは以下の論文で記載されている内容になります。
Jain, P., 2008. A simple in-place algorithm for in-shuffle. arXiv preprint arXiv:0805.1598.
https://arxiv.org/abs/0805.1598
順列とcycle list
アルゴリズムの出力は入力の並べ替えとなります。
このとき、$A[i]$の移動先を示した配列$B$を考えると、この$B$は$A$のインデックスの順列となります。
例えば$B=(2, 4, 6, 1, 3, 5)$は$A=(1, 2, 3, 4, 5, 6)$の順列となり、$B[i]$は$A[i]$の移動先を表しています。
この順列を自由に参照することができれば、in-shuffleが実現できます。
ただし、追加領域をいま使えないですので、そうすると色々と工夫が必要です。
順列の性質をもう少し考えてみましょう。
順列は各要素が示す先をつなげたcycleのlistで表現することができます。
例えば$B=(2, 4, 6, 1, 3, 5)$の場合、位置$1$から始めると、$B[1]=2$、$B[2]=4$と辿り、$B[4]=1$で最初の$1$へと戻ってきます。同様のcycleを考えると$B[3]=6, B[6]=5, B[5]=3$となり、順列$B$は$(1, 2, 4)$というサイクルと$(3, 6, 5)$という2つのサイクルで表現することができます。
なぜわざわざこんなcycle listを紹介したかというとこのcycle listがin-placeに並び替えるための重要な性質を持っているからです。
| cycleの性質 |
|---|
| cycleはin-placeに並べ替えが可能 |
各cycleは移動先を表しているので、cycleの先頭から対応する値を移動先へ保存し、もともと移動先に保存していた値を今度は次の移動先へと保存し、ということを繰り返すことで要素１個の保存領域でcycleどおりに値をin-placeに移動することができます。このアルゴリズムをcycle leaderアルゴリズムと呼びます。
$(1, 2, 4)$のサイクルをcycle leaderアルゴリズムで移動する例を見てみましょう
- $A[1]=1$から移動を始める
- $A[2]=2$の値を覚えておく
- $A[2]$に$1$を保存
- $A[4]=4$の値を覚えておく
- $A[4]に2$を保存
- $A[1]$に$4$を保存
このアルゴリズムにより、$A=(1, 2, 3, 4, 5, 6)$から$(4, 1, 3, 2, 5, 6)$へin-placeに変換することができました。
同様に$(3, 6, 5)$のcycleを使い移動すると、目的となる$A'=(4, 1, 5, 2, 6, 3)$を得ることができます。
この性質を利用してcycle listを効率よく求めることができれば、in-place in-shuffleが実現できます。
原始根
実は$2n=3^k-1$の形をとるときin-place in-shuffleは簡単に計算できます。
そのためには次の数論の定理を用います。
| 定理 |
|---|
| $p$が奇数素数、$g$が$p^2$の原始根のとき、$g$は$p^k$の原始根でもある。 W. Narkiewicz. The Development of Prime Number Theory: From Euclid to Hardy and Littlewood. Springer Monographs in Mathematics, New York. 2000 |
原始根という耳慣れないワードが出てきましたね。このあたりの説明をこれから行いますが、僕は数論に関して素人でこのあたりの説明はもしかしたら間違いかもしれないのでご注意ください。
$\phi(n)$は$n$と互いに素な1以上$n$以下の数の個数を表すもので、オイラーのϕ関数と呼ばれています。
（中略）
$a$を整数、$n$を2以上の整数で、$a,n$は互いに素とします。このとき、$a^k\equiv 1 (\text{mod } n)$を満たす最小の正の整数$k$を、$n$を法とする$a$の位数（order of $a$ modulo $n$）と呼びます。これを$k=ordn(a)$と書くことがあります。
また、$a$の位数が$\phi(n)$であるとき、$a$を整数$n$の原始根（primitive root of $n$）と呼びます。
整数の位数、原始根とその性質 オイラーの判定条件への応用 | 趣味の大学数学
例として$n=3$を考えましょう、$1$以上$n$以下で互いに素な数は$1, 2$なので$\phi(3)=2$です。
$a=1$を考えると$1^k \equiv 1 (\text{mod }3)$を満たす最小の$k$、位数は$1$となり、$\phi(3)=2$とは異なるので$a=1$は$n$の原始根ではありません。
$a=2$を考えると$2^k \equiv 1 (\text{mod }3)$を満たす最小の$k$、位数は2となり、$\phi(3)=2$と一致するため$a=3$は$n$の原始根となります。
原始根には次の性質があります。
原始根はべき乗すると互いに素な値をすべて生成する
整数の位数、原始根とその性質 オイラーの判定条件への応用 | 趣味の大学数学
$a=2, n=3$のとき、$2^1 (\text{mod }3)=2, 2^2 (\text{mod }3)=1$となり、$3$と互いに素な値をすべて生成します。
原始根とin-shuffle
それではさきほど説明した定理に立ち戻りましょう。
$2$は$3^2$の原始根となります。ですので定理より$2$は$3^k$ for $k \geq 1$の原始根となります。
ここで$2n=3^k-1$の場合を考えましょう。
原始根の性質より$2^1 (\text{mod }3^k), 2^2 (\text{mod }3^k), 2^3 (\text{mod }3^k), ..., 1$は自分の位置の$2$倍を指すin-shuffleのcyclic listの1つを表します。
このcyclic listは$3^k$と互いに素な、つまり3の倍数を含まないcyclic listを表しています。
もし、in-shuffleの他のcyclic listを効率的に求めることができれば、in-place in-shuffleを実現できそうです。
そのようなcyclic listは簡単に求めることができます。すべてのcyclic listは$3^s$ for $0 \leq s < k$を起点とし、そのcyclic listの要素は$3^s 2^t (\text{mod }3^k)$で表すことができます。
例として$2n=3^2-1=8$の場合を考えます。
$A=(1, 2, 3, 4, 5, 6, 7, 8)$のin-shuffleは$A'=(5, 1, 6, 2, 7, 3, 8, 4)$、順列は$B=(2, 4, 6, 8, 1, 3, 5, 7)$、cyclic listは$(2, 4, 8, 7, 5, 1)$と$(3, 6)$の２つとなります。
ここでそれぞれのcyclic listは$3^02^s$と$32^s$という形になっており、期待する形になっていることが確認できます。
以上より、$2n=3^k-1$の場合in-shuffleのcyclic listは領域無しで計算することができ、cycle leaderアルゴリズムを使うと各cycle listに含まれる要素をin-placeに移動することが出来るため、in-place in-shuffleを実現することができます。
一般的なin-place in-shuffle
それでは一般の入力サイズ$2n$で計算する方法を考えましょう。
$2m=3^k-1$の形を作れば、in-place in-shuffleが可能なため、$2n$の中にそのような部分問題を作り上げることで一般的な$2n$についてin-place in-shuffleを実現します。
$2m=3^{k-1}$ s.t. $3^k \leq 2n < 3^{k+1}$とします。
つまり、$2m$は$A$の内部でin-place in-shuffleが可能な最大サイズを表します。
$A'[1..2m]$は$A[1..m]$と$A[n/2+1..n/2+m]$をin-shuffleした配列になります。
ですので$A[1..2m]$に$A[1..m]$と$A[n/2+1..n/2+m]$を移動すれば、in-place in-shuffleできます。
ということでまず次のような変換を施します。
実際には$A$を書き換えますが、混乱を避けるため、$A$と書くとオリジナルの配列、書き換えた配列を$X$と表記することにします。
この変換は線形時間in-placeで計算することができます。
$X[1..2m]$についてin-place in-shuffleを行い$X[1..2m]=A'[1..2m]$を作成します。
あとは残りの$X[2m+1..2n]$について$X[2m+1..2n]=A'[2m+1..2n]$を作成すればよいのですが、ちょうど今$X[2m+1..2n]=A[m+1..n]A[n+m+1..2n]$と残りのin-shuffle対象となる配列２つが連続しています。
つまり、残りの$X[2m+1..2n]$に対して再帰的にin-place in-shuffleを適用すれば出力である$A'$全体が計算できるわけです。
以上より残りの要素についても再帰的にin-place in-shuffleを行うことで、$A$全体のin-shuffleをin-placeに計算することができます。
計算量解析
再帰呼び出しするまでは$O(m)$で実行することができ、残りの部分問題サイズは$2n-2m$となるため、全体として線形時間で計算することができます。
領域についてはcycle leaderアルゴリズムで要素を一時的に確保する領域が必要ですが、たかだか定数サイズに収まり、全体としてin-placeで動作します。
以上よりin-shuffleを線形時間in-placeに実行することができます。
Proof of Code
def reverse(arr, beg, end):
"""
reverse arr[beg:end] in-place.
"""
for i in range((end - beg) // 2):
arr[beg + i], arr[end - i - 1] = arr[end - i - 1], arr[beg + i]
def swap(arr, beg, mid, end):
"""
swap arr[beg:mid] and arr[mid:end] in-place.
"""
# print(f"swap {''.join(arr[beg:mid])}, {''.join(arr[mid:end])}")
reverse(arr, beg, mid)
reverse(arr, mid, end)
reverse(arr, beg, end)
def in_shuffle_in_place(arr: list, beg, end):
"""
in-shuffle arr[beg:end] in-place.
"""
# print(f"in_shuffle arr[{beg}:{end}]")
n2 = end - beg
assert n2 % 2 == 0
if n2 == 0:
return
if n2 <= 2:
arr[beg], arr[beg + 1] = arr[beg + 1], arr[beg]
return
def largestk(n2):
k3 = 1
res = 0
while k3 <= n2:
res += 1
k3 *= 3
return res - 1, k3 // 3
k, k3 = largestk(n2)
n1 = n2 // 2
m2 = k3 - 1
m1 = m2 // 2
# print(f"arr[{beg}:{end}], k3={k3}, n2={n2}, m2={m2}")
# print(f"swap(arr, {beg+m1}, {beg+n1}, {beg+m1+n1})")
swap(arr, beg + m1, beg + n1, beg + m1 + n1)
# print(f"arr[{beg}:{end}]={''.join(arr[beg:end])}")
for ki in range(k):
start = 3 ** ki
prev = arr[beg + start - 1]
cur = (start * 2) % k3
while True:
arr[beg + cur - 1], prev = prev, arr[beg + cur - 1]
if cur == start:
break
cur = (cur * 2) % k3
# print(
# f"inshuffle done arr[{beg}:{beg+m2}]={''.join(arr[beg:beg+m2])}, arr={''.join(arr)}"
# )
in_shuffle_in_place(arr, beg + m2, end)
def in_shuffle_naive(arr, beg, end):
n2 = end - beg
assert n2 % 2 == 0
arr2 = arr[:]
n1 = n2 // 2
for i in range(n1):
arr[2 * i] = arr2[n1 + i]
arr[2 * i + 1] = arr2[i]
if __name__ == "__main__":
arr = list("abcdefghi123456789")
arr2 = arr.copy()
print(f"origin = {''.join(arr)}")
res = in_shuffle_in_place(arr, 0, len(arr))
print(f"in-place = {''.join(arr)}")
in_shuffle_naive(arr2, 0, len(arr2))
print(f"naive = {''.join(arr2)}")
実行結果
$ python inshuffle_poc.py
origin = abcdefghi123456789
in-place = 1a2b3c4d5e6f7g8h9i
naive = 1a2b3c4d5e6f7g8h9i
その他
同様の考え方でin-shuffleした配列を元の配列にin-placeで戻すこともできます。
An in-place algorithm for String Transformation - GeeksforGeeks