皆さん一度は、あみだくじを触ったことがあると思います。X(旧twitter)で流れてきたポストをきっかけに、あみだくじについて色々と考えてみましたので共有します。
投稿者は数学が専門ではなく、用語の使い方が正確ではないかもしれません。ご了承の上、お付き合いください。
この記事で考える問題
以下の問題について、色々と考察していきます。
[問題] あみだくじ変換
順列$X$を順列$Y$に変換する「あみだくじ」を、 あみだくじ変換 と定義します。
順列$X$に対して あみだくじ変換 を繰り返し適用することで、いずれ元の順列$X$に戻ることが知られています。
順列の要素数が$N$の場合に、最も多く繰り返して元の順列に戻る あみだくじ変換 を選ぶと、何回の あみだくじ変換で元の順列に戻るでしょうか。
経緯
元ネタ
先日Xで次のようなポストを目にしました。
数学の先生が教えてくれた「小学2年生の算数」がマジで難しくてビックリだったんですけれど…
— 地理おた部 ～高校地理お助け部～ (@geographybu) May 28, 2024
これ皆さんわかりますか…？
一応簡単に解ける方法もあるみたいなのですが… pic.twitter.com/QqZpT3wHtg
この問題では6入力のあみだくじを考えています。あみだくじが一つ挙げられ、そのあみだくじを適用すると、$(1,2,3,4,5,6)$の並びが、$(6,4,1,2,5,3)$となります。「この変換を何回適用すれば、もとの並びに戻りますか？」というのが、この問題です。
このあみだくじを改めて図示したのものが下記左側の図です。右図は変換結果のみに着目して矢印で記載しました。
元の状態$(1,2,3,4,5,6)$には、このあみだくじを6回適用することで戻ります。
よって、この問題の答えは6回です。小学校2年生の算数の問題ですが、結構考えさせられますね。小学生2年生に期待する解答は、もとの状態になるまで、繰り返しあみだくじを適用してみて解くことなのでしょうか。
この問題を考えているうちに…
ここで一つの疑問が湧きます。もっとも繰り返し適用しなければ元の状態に戻らない あみだくじ変換 とは、どのような変換でしょうか。また、あみだくじの要素数が増えると、繰り返し回数はどのようになるのでしょうか。
それを競技プログラミングの問題文っぽくしてみたのが、本記事の最初に記載した内容です。
[問題] あみだくじ変換（再掲）
順列$X$を順列$Y$に変換する「あみだくじ」を、 あみだくじ変換 と定義します。
順列$X$に対して あみだくじ変換 を繰り返し適用することで、いずれ元の順列$X$に戻ることが知られています。
順列の要素数が$N$の場合に、最も多く繰り返して元の順列に戻る あみだくじ変換 を選ぶと、何回の あみだくじ変換で元の順列に戻るでしょうか。
必要な繰り返し回数が多い あみだくじ変換 を「効率の悪いあみだくじ変換」と呼ぶことにします。任意の要素数$N$に対して一般化できれば良いのですが、要素数$N=100$の あみだくじ変換 についての答えを出すことをこの記事の目標とします。
6要素のあみだくじの場合
まずは例題にもある$6$要素の場合を考えてみます。他に思いつく変換としては、$1$要素ずつシフトする変換が挙げられます。
こちらも$6$回の変換で元の順列に戻ります。この操作では、$6$個の要素を順番にシフトして入れ替えているので、$6$回の変換で元に戻ると考えられます。
対して例題の変換では、どのように入れ替えていたでしょうか。改めて確認してみると、3つのパターンに分けられることがわかります。
まず5番目の要素に着目すると、入れ替わりをしていません。これがパターン1です。
パターン2は2番目と4番目の要素で、こちらは変換ごとに、交互に入れ替わってることがわかります。最後のパターン3は、1番目と3番目、6番目の要素の入れ替え操作で、3回の変換で1周していることがわかります。このことから、例題の変換パターンでは、「1回周期の変換」と「2回周期の変換」、「3回周期の変換」が組み合わさっており、1,2,3の最小公倍数である6回の変換で元の順列に戻ったと説明できます。
要素数Nの場合を、プログラムで計算してみる
ここまでに、要素数6の場合を2パターン考えてみました。しかしもっと効率の悪い あみだくじ変換 はないのでしょうか。要素数が少ない場合には、組み合わせもあまり多くならず、コンピュータで総当り計算できそうです。
作戦1：総当たりでの計算
そこでまずは次のアプローチでプログラムを実装し、効率の悪いあみだくじ変換を調べてみることにしました。
- N要素入力に対応する、$(1, 2, ..., N)$の配列を用意する
- 入れ替え関数(itertools.permutations)を利用して、全てのあみだくじ変換を作成する
- 配列$(1, 2, ..., N)$に対して、元の配列に戻るまで、繰り返しあみだくじ変換を適用する
- 最大の繰り返し回数が更新されたら、繰り返し回数とあみだくじ変換を更新する
プログラムはPython3で作成しました。入力要素数は引数Nで指定します。
ソースコードはここをクリック
import itertools
import time
import sys
def main(N):
box = list(range(N))
start_time = time.time()
answer = 0
max_it = 0
for it in itertools.permutations(box):
current = box.copy()
count = 0
while True:
count += 1
after = amd(current, list(it))
if after == box:
break
else:
current = after
if count > answer:
answer = count
max_it = it
end_time = time.time()
print("max steps :",answer)
print("max filter:",[x+1 for x in max_it])
print("time", round(end_time-start_time, 5), "[s]")
def amd(now, method):
box_len = len(now)
after = [0]*box_len
for i in range(box_len):
after[i] = now[method[i]]
return after
if __name__ == "__main__":
args = sys.argv
main(int(args[1]))
総当たりでの、計算結果
$N=12$まで計算した結果を下記に示します。
| N | 最大繰り返し[回] | 変換パターン | 計算時間 [s] |
|---|---|---|---|
| 1 | 1 | [1] | 0.0 |
| 2 | 2 | [2, 1] | 1e-05 |
| 3 | 3 | [2, 3, 1] | 2e-05 |
| 4 | 4 | [2, 3, 4, 1] | 4e-05 |
| 5 | 6 | [2, 1, 4, 5, 3] | 0.00042 |
| 6 | 6 | [1, 3, 2, 5, 6, 4] | 0.00196 |
| 7 | 12 | [2, 3, 1, 5, 6, 7, 4] | 0.01833 |
| 8 | 15 | [2, 3, 1, 5, 6, 7, 8, 4] | 0.18475 |
| 9 | 20 | [2, 3, 4, 1, 6, 7, 8, 9, 5] | 2.20715 |
| 10 | 30 | [2, 1, 4, 5, 3, 7, 8, 9, 10, 6] | 27.05151 |
| 11 | 30 | [1, 3, 2, 5, 6, 4, 8, 9, 10, 11, 7] | 396.45285 |
| 12 | 60 | [2, 3, 1, 5, 6, 7, 4, 9, 10, 11, 12, 8] | 5555.85327 |
まず計算時間ですが、$N$が1増えるごとに計算時間が1桁増えており、この方法での計算は$N=12$までで断念しました。
それでは効率の悪いあみだくじ変換を確認しましょう。要素数が増えるにつれて最大繰り返し回数は飛躍的に増えています。しかし$N=5$および$N=6$がどちらも$6$回だったり、$N=10$と$N=11$がどちらも30だったりと、単純に要素数$N$が大きければ、最大繰り返し回数が増えるわけではないようです。
なお、このプログラムでは先の要素数6の例のように、最大繰り返し回数が同じ場合には、少ない周期の変換の組み合わせを優先するようにしています。
例：周期$6$よりも、周期$1$+周期$2$+周期$3$を優先します。
ここで$N=10$の場合の変換パターンの周期に着目すると、次の図のようになります。
周期$2,3,5$が繰り返されており、最小公倍数である$30$回変換することで、元の配列に戻ることがわかります。このように各要素数での変換パターンの周期に着目して、改めて表をまとめると次のようになります。
| N | 最大繰り返し[回] | 周期 |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| 3 | 3 | 3 |
| 4 | 4 | 4 |
| 5 | 6 | 2, 3 |
| 6 | 6 | 1, 2, 3 |
| 7 | 12 | 3, 4 |
| 8 | 15 | 3, 5 |
| 9 | 20 | 4, 5 |
| 10 | 30 | 2, 3, 5 |
| 11 | 30 | 1, 2, 3, 5 |
| 12 | 60 | 3, 4, 5 |
$N=5$以上では、最大繰り返し数は複数の周期の最小公倍数となっています。この最小公倍数というキーワードからも明らかですが、最も効率の悪いあみだくじ変換では、変換内の各周期は互いに素の関係になっています。
例：$N=12$の場合の周期$3,4,5$は、最大公約数1であり、互いに素です。
また、周期として登場する数字に着目すると、奇数か2のべき乗に限られているようです。1
この観点に着目して、もう少し計算量の少ない方法で、効率の悪いあみだくじ変換を考えることにします。
作戦2：候補となる周期を絞って探索
今度は次のアプローチで、探索を行いました。
- 周期候補配列として$(1, 2, ..., M)$を用意し、2のべき乗以外の偶数を除外する
- 組み合わせ関数(itertools.combinations)を使用して、候補周期の組み合わせを作る
- 候補周期の組み合わせの和と積を計算し、和ごとの積の最大値(繰り返し回数)を記録する
- 1から順に和ごとの積の最大値を出力する
プログラムはPython3で作成しました。探索する候補周期の最大値は引数$M$で指定します。
ソースコードはここをクリック
import itertools
import sys
import math
import time
def main(N):
# 候補となりうる数値のリスト
value_list = list(range(1,N+1))
# value_listから2^N以外の偶数を除外する
mod_list = []
for i in range(N):
if (value_list[i] % 2 == 0) and is_pow2(value_list[i])==False:
continue
mod_list.append(value_list[i])
value_list = mod_list.copy()
value_sum = int((N+1)*N/2)
N_max_val = [0]*(value_sum+1)
N_max_conv = [[0]]*(value_sum+1)
highest = 0
start_time = time.time()
for i in range(1,N+1):
for ic in itertools.combinations(value_list,i):
# 各要素の約数の重なりを確認
if each_independ(ic) == False:
continue
current_sum = sum(ic)
current_prod = math.prod(ic)
# scoreを更新した場合には、上書きする
if current_prod > N_max_val[current_sum]:
N_max_val[current_sum] = current_prod
N_max_conv[current_sum] = ic
highest = max(current_prod, highest)
end_time = time.time()
# 結果出力
current_max_val = 0
current_max_conv = []
for i in range(1,value_sum+1):
if N_max_val[i] > current_max_val:
print(i, ":" , N_max_val[i], list(N_max_conv[i]))
current_max_val = N_max_val[i]
current_max_conv = list(N_max_conv[i])
else:
if highest == current_max_val:
print("finish!!!")
break
missing_num = i - sum(current_max_conv)
alternative_conv = [1]*missing_num + current_max_conv
print(i, ": *" , current_max_val, alternative_conv)
print("time", round(end_time-start_time, 5), "[s]")
# リストの全要素が互いに1以外の約数を含まないか判定
def each_independ(v_list):
current_element = []
for i in range(len(v_list)):
i_div = divisor(v_list[i])
for div_key in i_div:
if div_key == 1:
continue
if div_key not in current_element:
current_element.append(div_key)
else:
return False
return True
# 約数列挙
def divisor(n):
i = 1
ans = []
while i*i <= n:
if n % i == 0:
ans.append(i)
ans.append(n//i)
i+=1
ans = sorted(list(set(ans)))
return ans
# 2のべき乗判定
def is_pow2(x):
if x == 0:
return False
return (x & (x - 1)) == 0
if __name__ == "__main__":
args = sys.argv
main(int(args[1]))
探索結果
探索周期最大を$M=47$と設定した場合の、要素数$N=100$までの結果を書きに記載します。2
| N | 最大繰り返し[回] | 周期 |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| 3 | 3 | 3 |
| 4 | 4 | 4 |
| 5 | 6 | 2, 3 |
| 6 | * 6 | 1, 2, 3 |
| 7 | 12 | 3, 4 |
| 8 | 15 | 3, 5 |
| 9 | 20 | 4, 5 |
| 10 | 30 | 2, 3, 5 |
| 11 | * 30 | 1, 2, 3, 5 |
| 12 | 60 | 3, 4, 5 |
| 13 | * 60 | 1, 3, 4, 5 |
| 14 | 84 | 3, 4, 7 |
| 15 | 105 | 3, 5, 7 |
| 16 | 140 | 4, 5, 7 |
| 17 | 210 | 2, 3, 5, 7 |
| 18 | * 210 | 1, 2, 3, 5, 7 |
| 19 | 420 | 3, 4, 5, 7 |
| 20 | * 420 | 1, 3, 4, 5, 7 |
| 21 | * 420 | 1, 1, 3, 4, 5, 7 |
| 22 | * 420 | 1, 1, 1, 3, 4, 5, 7 |
| 23 | 840 | 3, 5, 7, 8 |
| 24 | * 840 | 1, 3, 5, 7, 8 |
| 25 | 1260 | 4, 5, 7, 9 |
| 26 | * 1260 | 1, 4, 5, 7, 9 |
| 27 | 1540 | 4, 5, 7, 11 |
| 28 | 2310 | 2, 3, 5, 7, 11 |
| 29 | 2520 | 5, 7, 8, 9 |
| 30 | 4620 | 3, 4, 5, 7, 11 |
| 31 | * 4620 | 1, 3, 4, 5, 7, 11 |
| 32 | 5460 | 3, 4, 5, 7, 13 |
| 33 | * 5460 | 1, 3, 4, 5, 7, 13 |
| 34 | 9240 | 3, 5, 7, 8, 11 |
| 35 | * 9240 | 1, 3, 5, 7, 8, 11 |
| 36 | 13860 | 4, 5, 7, 9, 11 |
| 37 | * 13860 | 1, 4, 5, 7, 9, 11 |
| 38 | 16380 | 4, 5, 7, 9, 13 |
| 39 | * 16380 | 1, 4, 5, 7, 9, 13 |
| 40 | 27720 | 5, 7, 8, 9, 11 |
| 41 | 30030 | 2, 3, 5, 7, 11, 13 |
| 42 | 32760 | 5, 7, 8, 9, 13 |
| 43 | 60060 | 3, 4, 5, 7, 11, 13 |
| 44 | * 60060 | 1, 3, 4, 5, 7, 11, 13 |
| 45 | * 60060 | 1, 1, 3, 4, 5, 7, 11, 13 |
| 46 | * 60060 | 1, 1, 1, 3, 4, 5, 7, 11, 13 |
| 47 | 120120 | 3, 5, 7, 8, 11, 13 |
| 48 | * 120120 | 1, 3, 5, 7, 8, 11, 13 |
| 49 | 180180 | 4, 5, 7, 9, 11, 13 |
| 50 | * 180180 | 1, 4, 5, 7, 9, 11, 13 |
| 51 | * 180180 | 1, 1, 4, 5, 7, 9, 11, 13 |
| 52 | * 180180 | 1, 1, 1, 4, 5, 7, 9, 11, 13 |
| 53 | 360360 | 5, 7, 8, 9, 11, 13 |
| 54 | * 360360 | 1, 5, 7, 8, 9, 11, 13 |
| 55 | * 360360 | 1, 1, 5, 7, 8, 9, 11, 13 |
| 56 | * 360360 | 1, 1, 1, 5, 7, 8, 9, 11, 13 |
| 57 | 471240 | 5, 7, 8, 9, 11, 17 |
| 58 | 510510 | 2, 3, 5, 7, 11, 13, 17 |
| 59 | 556920 | 5, 7, 8, 9, 13, 17 |
| 60 | 1021020 | 3, 4, 5, 7, 11, 13, 17 |
| 61 | * 1021020 | 1, 3, 4, 5, 7, 11, 13, 17 |
| 62 | 1141140 | 3, 4, 5, 7, 11, 13, 19 |
| 63 | * 1141140 | 1, 3, 4, 5, 7, 11, 13, 19 |
| 64 | 2042040 | 3, 5, 7, 8, 11, 13, 17 |
| 65 | * 2042040 | 1, 3, 5, 7, 8, 11, 13, 17 |
| 66 | 3063060 | 4, 5, 7, 9, 11, 13, 17 |
| 67 | * 3063060 | 1, 4, 5, 7, 9, 11, 13, 17 |
| 68 | 3423420 | 4, 5, 7, 9, 11, 13, 19 |
| 69 | * 3423420 | 1, 4, 5, 7, 9, 11, 13, 19 |
| 70 | 6126120 | 5, 7, 8, 9, 11, 13, 17 |
| 71 | * 6126120 | 1, 5, 7, 8, 9, 11, 13, 17 |
| 72 | 6846840 | 5, 7, 8, 9, 11, 13, 19 |
| 73 | * 6846840 | 1, 5, 7, 8, 9, 11, 13, 19 |
| 74 | * 6846840 | 1, 1, 5, 7, 8, 9, 11, 13, 19 |
| 75 | * 6846840 | 1, 1, 1, 5, 7, 8, 9, 11, 13, 19 |
| 76 | 8953560 | 5, 7, 8, 9, 11, 17, 19 |
| 77 | 9699690 | 2, 3, 5, 7, 11, 13, 17, 19 |
| 78 | 12252240 | 5, 7, 9, 11, 13, 16, 17 |
| 79 | 19399380 | 3, 4, 5, 7, 11, 13, 17, 19 |
| 80 | * 19399380 | 1, 3, 4, 5, 7, 11, 13, 17, 19 |
| 81 | * 19399380 | 1, 1, 3, 4, 5, 7, 11, 13, 17, 19 |
| 82 | * 19399380 | 1, 1, 1, 3, 4, 5, 7, 11, 13, 17, 19 |
| 83 | 38798760 | 3, 5, 7, 8, 11, 13, 17, 19 |
| 84 | * 38798760 | 1, 3, 5, 7, 8, 11, 13, 17, 19 |
| 85 | 58198140 | 4, 5, 7, 9, 11, 13, 17, 19 |
| 86 | * 58198140 | 1, 4, 5, 7, 9, 11, 13, 17, 19 |
| 87 | * 58198140 | 1, 1, 4, 5, 7, 9, 11, 13, 17, 19 |
| 88 | * 58198140 | 1, 1, 1, 4, 5, 7, 9, 11, 13, 17, 19 |
| 89 | 116396280 | 5, 7, 8, 9, 11, 13, 17, 19 |
| 90 | * 116396280 | 1, 5, 7, 8, 9, 11, 13, 17, 19 |
| 91 | * 116396280 | 1, 1, 5, 7, 8, 9, 11, 13, 17, 19 |
| 92 | * 116396280 | 1, 1, 1, 5, 7, 8, 9, 11, 13, 17, 19 |
| 93 | 140900760 | 5, 7, 8, 9, 11, 13, 17, 23 |
| 94 | * 140900760 | 1, 5, 7, 8, 9, 11, 13, 17, 23 |
| 95 | 157477320 | 5, 7, 8, 9, 11, 13, 19, 23 |
| 96 | * 157477320 | 1, 5, 7, 8, 9, 11, 13, 19, 23 |
| 97 | 232792560 | 5, 7, 9, 11, 13, 16, 17, 19 |
| 98 | * 232792560 | 1, 5, 7, 9, 11, 13, 16, 17, 19 |
| 99 | * 232792560 | 1, 1, 5, 7, 9, 11, 13, 16, 17, 19 |
| 100 | * 232792560 | 1, 1, 1, 5, 7, 9, 11, 13, 16, 17, 19 |
※最大繰り返し回数に記載した"$*$"マークは、一つ以上前の要素数と同じ回数の場合を示しています。
周期に着目すると、最大繰り返し回数にするためには各周期を互いに素に設定する必要があるため、素数が多く出現しています。ひとまず目標としていた要素数$N=100$について、232,792,560回繰り返すことで、元の状態に戻ることが分かりました。答えは2億回以上と、要素数$N=100$あたりになると、効率の悪い あみだくじ変換 では、非常に多くの回数適用しなければ、元の状態に戻らないことが分かりました。
ちょっとした考察
ここまでの検討を通じて分かったことをまとめます。
- ($N=5$以上の場合) 効率の悪いあみだくじは、内部に周期の異なる繰り返しを持つ
- 各周期は、いずれも互いに素の関係になる
- 周期には奇数と2のべき乗が登場し、奇数の中でも素数が多く登場する
$N$が小さい領域を考えてみると、要素数が$1$ずつ増えるにつれて効率の悪いあみだくじ変換の周期が、どのように変わっていくのかわかります。$N=20$までの成長を図示してみます。
以下の図では四角形を、あみだくじ変換内に含まれる周期として使っています。
基本的に要素数が1増えたとのパターンは、以下のいずれかになりそうです。
- いずれかの周期を$+1$する (例：$N=8$から$N=9$)
- 複数の周期を結合し、$+1$する (例：$N=6$から$N=7$)
- 周期を$+1$し複数に分割する (例：$N=9$から$N=10$)
- 周期$1$を新たに追加する (例：$N=5$から$N=6$)
- 複数の周期を結合し、$+1$をした上で、複数に分割する (例：$N=63$から$N=64$)
※$N=63$の周期$1,4,19$を結合し、$1$を足して、$8,17$に分割する。
ここに挙げたパターンを試してみて、最大のものを選ぶ方式でプログラミングを行えば、もう少し効率よく探索できるかもしれません。(ここで挫折)
最後に
効率の悪い「あみだくじ変換」について、ある程度調べることができました。
目標としていた要素数$N=100$のあみだくじに対して、どのような あみだくじ変換 が効率が悪いのか見通すことができました。
しかし更なる目標である一般化まではできていません。
どうやら群論・周期群？などを理解すれば、もっと深く説明できそうですが…。
数学が得意な方のコメント・解説などお待ちしています！
ここまで読んでくださって、ありがとうございました！
-
$N=12$までの結果を見ている時点では、偶数が2のべき乗に限られることには気がついていなかったのですが、その後色々試行錯誤する中で、2のべき乗のみに限られることに気が付きました。 ↩
-
このスクリプトは引数$M$で候補周期の最大値を指定し、その範囲内で探索を行います。
そのため要素数$N$に対して候補周期$M$の指定が小さい場合に、最低効率以外のあみだくじ変換が出力される場合があります。
例1：$M=19$で探索した場合の出力
95 : 116396280 [1, 1, 1, 1, 1, 1, 5, 7, 8, 9, 11, 13, 17, 19]
例2：$M=23$で探索した場合の出力
95 : 157477320 [5, 7, 8, 9, 11, 13, 19, 23] ↩