プレゼントに困ったら列挙をしよう

Last updated at 2017-12-25Posted at 2017-12-24

みなさん，クリスマスですか？クリスマスですね．プレゼントしますか？プレゼントしますね．ネックレスですか？ネックレスですね．どのネックレスをあげますか？よくわかりませんね．たくさんありますし．とりあえず列挙して，その中から選びたくなりますね．さて，列挙しましょうか．急ぎましょう．今ならまだ間に合います！

#ネックレス
列挙の前にネックレスの定義です．ネックレスとは，次の制約を満たすビーズの列をいいます：
$k$種類のビーズからなる長さ$n$のビーズ列$\alpha = \alpha_1 \dots \alpha_n$がネックレスであるとは，任意の$1 \le i \le n$について，$\alpha_1 \dots \alpha_n \le \alpha_i \dots \alpha_n \alpha_1 \dots \alpha_{i-1}$を満たすときをいいます．
例えば，$0011$はネックレスですが，$1100$はネックレスではないです．ほかにも$039216$はネックレスですが，$921603$はネックレスではないです．ネックレスはグルッと回しても同じ形ですもんね．この定義はしっくりきます．ということで，あなたのパートナーが欲しがるネックレスは必ずこの条件を満たしているはずです（そうでなければネックレスではありません）．

#ネックレスの列挙
じゃあ，列挙しましょうか．列挙といいましたが，列挙とは何でしょうか．ここでの列挙とは，「ある制約が与えられたときに，その制約を満たすものを漏れなく重複なく，出力すること」です．たとえば，「初代ポケモンをすべて答えよ」が身近にある例ですね．この問題の解法の一つは，「ポケモン言えるかな」を利用する手法です¹．

ネックレスの列挙は次のように定義されます：ネックレスの列挙とは，ある2つの整数$n, k$が与えられたときに，長さ$n$で$k$種類のビーズ列からなるネックレスを漏れなく重複なく出力すること．ビーズを文字と読み替えると，見事に文字列の列挙問題になりますね．さて，この問題を解く愚直な方法はなんでしょうか．総当りですね．つまり，ありうる文字列すべてをチェックして，ネックレスになるものだけ出力する，という方法です．

ところで，$k$種類の文字からなる長さ$n$の文字列は，$A(n, k) = k^n$個あります．総当りでは，この数の文字列をチェックします．たくさんありますね．では，ネックレスは何種類あるでしょうか．Mackiw²によると$N(n, k) = \frac{1}{n}\sum_{i=1}^{n}k^{gcd(i,n)}$個あるらしいです．わかりにくいですが，これは，$\frac{1}{n}k^n \le N(n, k) \le \frac{1}{n}(k^n + (n-1)k^{\frac{n}{2}})$を満たします．たくさんありますね．あ！$A(n, k)$よりも$N(n, k)$が$n$倍以上多くなってしまいます！．これは大変です．なぜかというと，総当りで列挙してしまうと，解1つを計算するのに$n$個くらい無駄な文字列をチェックしなくてはいけないことを意味します．

「このままではプレゼントに間に合わない！！！この記事を読んで時間を無駄にしたじゃないか！！！！」とご心配のあなた．安心してください．いいニュースがあります．Fredricksen, Kessler, Maioranaというネックレスマニアが解1つあたり$\mathcal{O}(1)$時間で列挙するFKMアルゴリズムを与えました³⁴．つまり，無駄打ちは高々定数回であるような最適アルゴリズムを提案しました．しかも辞書順で出力してくれます！！⁵

#列挙しよう
FredricksenらのアルゴリズムのPascalコードを次に与えます．コード中のaはネックレスになる文字列を格納する配列です．

for i := 0 to n do a[i] = 0
Print(a)
i := 0
repeat
   a[i] := a[i] + 1
   for j := 0 to n-i do a[j+i] = a[j]
   if n mod i = 0 then Print(a)
   i := n
   while a[i] = k-1 do i := i - 1
until i = 0

興味のない方は読み飛ばして良いですが，具体的にアルゴリズムがどんなことをやっているのかサラッと読んでみましょう．あるネックレス$\alpha$は，$\alpha = \alpha_1 \dots \alpha_i (k-1)^{n-i}$と記述できます．ただし，$i$は$\alpha_i < k - 1$を満たす最大の$i$とします．アルゴリズムでは，この$\alpha$に対し，次のように定義される文字列$succ(\alpha)$を計算します：
$$succ(\alpha) = (\alpha_1 \dots \alpha_{i-1}(\alpha_i+1))^t\alpha_1 \dots \alpha_j.$$
ただし，$i, j$は，$it + j = n$と$j < i$を満たすとします．おもしろいことに，もし$i$が$n$を割り切れば，$succ(\alpha)$はネックレスになっています．この性質を用いて，アルゴリズムは次のようにネックレスを列挙します：まず，$\alpha = 0^n$からスタートします．次に，$\alpha$の$succ$を計算します．もし$i$が$n$を割り切ったときに$succ(\alpha)$を出力します．これを$\alpha = (k-1)^n$に到達するまで再帰的に続けます．

次に，$succ$の具体的な例を見てましょう．以下では，$k=3, n=8$とします．例えば，$01112222 = 0111(3-1)^4$の$succ(01112222)$は，
$$succ(01112222) = (0112)^2 = 01120112$$
となります（$i = 4, t = 2, j = 0$）．このとき，$i = 4$が$n = 8$を割り切りますし，$01120112$はネックレスです．一方，$01110222 = 01110(3-1)^3$の$succ(01110222)$は，
$$succ(01110222) = (0111(0+1))^1011 = 01111011$$
ですが（$i = 5, t = 1, j = 3$），$i= 5$は$n = 8$を割り切りませんし，実際にネックレスではありません（$01101111 < 01111011$）．したがって，再帰的に$succ(01111011)$を求めると，
$$succ(01111011) = 01111012$$
となります（$i =8, t=1, j = 0$)．このとき，$i=8$は$n=8$を割り切りますし，$01111012$はネックレスです．詳細は省きましたが，なんとも不思議ですね．さて，準備ができたところで短いネックレスを列挙してみましょう．次は$n=4, k=3$のときです．

一見すると解1つあたり定数時間では列挙できないように見えますが，別のネックレスマニアRuskey, Savage, Wangによる解析により，上記のアルゴリズムは解1つあたり$\mathcal{O}(1)$時間で列挙できることが知られています⁶．すばらしい！これでプレゼントに間に合いました．とりあえず，列挙してお気に入りのネックレスを探してください．もし制約付きのネックレスやブレスレットをプレゼントするために列挙したいときは，列挙の列挙のページを参照してください．最後にpythonコードも貼っておきますね．

def printNecklace(a):
	print(''.join(map(str,a[1:])))

def FKM(n, k):
	a = [0]*(n+1)
	printNecklace(a)
	i = n
	while True:
		a[i] = a[i] + 1
		for j in range(1, n-i+1):
			a[j+i] = a[j]
		if n % i == 0:
			printNecklace(a)
		i = n
		while a[i] == k-1:
			i = i - 1
		if i == 0:
			break

if __name__ == '__main__':
    FKM(4,3)

最後に「ミュウ」と叫びましょう． ↩
Mackiw, G., (1985). Applications ofAbstract Algebra, Wiley, New York. ↩
Fredricksen, H., & J. Kessler, I. (1986). An algorithm for generating necklaces of beads in two colors. Discrete Mathematics, 61(2–3), 181–188. http://doi.org/10.1016/0012-365X(86)90089-0 ↩
Fredricksen, H., & Maiorana, J. (1978). Necklaces of beads in k colors and k-ary de Bruijn sequences. Discrete Mathematics, 23(3), 207–210. http://doi.org/10.1016/0012-365X(78)90002-X ↩
文字列の場合，比較的多くの対象が辞書順で列挙できますが，グラフの部分構造となると話は別です．例えば，全域木の列挙自体は一つあたり定数時間で列挙できます．しかし，全域木をコストの辞書順で列挙する，ならし多項式時間アルゴリズムは未だ知られていません．文字列は美しいですね． ↩
Ruskey, F., Savage, C., & Min Yih Wang, T. (1992). Generating necklaces. Journal of Algorithms, 13(3), 414–430. http://doi.org/10.1016/0196-6774(92)90047-G ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up