計算量ガン無視で与えられた語群の最長しりとりを求める話

概要

あまり深く考えずに Ruby で最長しりとり問題を解くプログラムを書いてみたら，計算量が大きくなりすぎて使い物にならなくなってしまったので供養する．なお，使い物になるプログラムについては，例えば下記の記事が参考になる．

• 最長しりとりを求めるプログラムを今更ながらに作ってみた - Qiita

詳細

語群は words.txt に保存しておく．このとき，文字コードは Shift JIS とする¹．

words.txt

ごりら
りんご
ぱんだ
らっぱ

実装

Step.1: 語群を配列に保存する

shiritori.rb

# 語群を配列に保存
words = readlines(chomp: true)
p words

コマンドプロンプトでの実行結果

>type words.txt | ruby shiritori.rb
["ごりら", "りんご", "ぱんだ", "らっぱ"]

Step.2: 語群と各単語の語頭・語尾をハッシュに保存する

shiritori.rb

# 語群を配列に保存
words = readlines(chomp: true)

# 語群と各単語の語頭・語尾をハッシュに保存
words_ht = {}
words.each {|word|
    words_ht[word] = [word[0],word[word.length-1]]
}

p words_ht

コマンドプロンプトでの実行結果

>type words.txt | ruby shiritori.rb
{"ごりら"=>["ご", "ら"], "りんご"=>["り", "ご"], "ぱんだ"=>["ぱ", "だ"], "らっぱ"=>["ら", "ぱ"]}

Step.3: 語群の全順列を求め，しりとりになっているものを語数と併せてハッシュに保存する

shiritori.rb

# 語群を配列に保存
words = readlines(chomp: true)

# 語群と各単語の語頭・語尾をハッシュに保存
words_ht = {}
words.each {|word|
    words_ht[word] = [word[0],word[word.length-1]]
}

# 語群の全順列を求め，しりとりになっているものを語数と併せてハッシュに保存
shiritoris = {}
words.permutation(words.length) {|perm|
    shiritori = []
    n = 0
    while (n < perm.length-1 && words_ht[perm[n]][1] == words_ht[perm[n+1]][0]) do
        n += 1
    end
    for i in 0..n do
        shiritori += [perm[i]]
    end

    shiritoris[shiritori] = shiritori.length
}

p shiritoris

コマンドプロンプトでの実行結果

>type words.txt | ruby shiritori.rb
{["ごりら"]=>1, ["ごりら", "らっぱ"]=>2, ["ごりら", "らっぱ", "ぱんだ"]=>3, ["りんご", "ごりら"]=>2, ["りんご", "ごりら", "ら 
っぱ", "ぱんだ"]=>4, ["りんご"]=>1, ["ぱんだ"]=>1, ["らっぱ"]=>1, ["らっぱ", "ぱんだ"]=>2}

Step.4: しりとりの中で単語数が最大のものを出力する

shiritori.rb

# 語群を配列に保存
words = readlines(chomp: true)

# 語群と各単語の語頭・語尾をハッシュに保存
words_ht = {}
words.each {|word|
    words_ht[word] = [word[0],word[word.length-1]]
}

# 語群の全順列を求め，しりとりになっているものを語数と併せてハッシュに保存
shiritoris = {}
words.permutation(words.length) {|perm|
    shiritori = []
    n = 0
    while (n < perm.length-1 && words_ht[perm[n]][1] == words_ht[perm[n+1]][0]) do
        n += 1
    end
    for i in 0..n do
        shiritori += [perm[i]]
    end

    shiritoris[shiritori] = shiritori.length
}

# しりとりの中で単語数が最大のものを出力
p shiritoris.max { |a, b| a[1] <=> b[1] }

コマンドプロンプトでの実行結果

>type words.txt | ruby shiritori.rb
[["りんご", "ごりら", "らっぱ", "ぱんだ"], 4]

計算量

上記のプログラムでは語群の全順列を求めているので，語数 $n$ に対し少なくとも $n!$ 回の計算が行われる．従って，$n$ が大きい場合には全く使い物にならない．実際，カントー図鑑のポケモン151匹で計算するとなれば

\log_{10}151!\fallingdotseq264.94

より計算量は $10^{264.94}\fallingdotseq8.7\times10^{264}$ 以上²となる．

おまけ: Python で実装

上記と同様のプログラムを Python で書くと，例えば次のようになる．Python ではハッシュのキーとして配列を用いられないことに注意．

shiritori.py

# -*- coding: utf-8 -*-
import codecs
import itertools

# 語群を配列に保存
wordsfile = codecs.open('words.txt', 'r', 'utf-8')
words = wordsfile.read().split()

# 語群と各単語の語頭・語尾をハッシュに保存
words_ht = {}
for word in words:
    words_ht[word] = [word[0],word[len(word)-1]]

# 語群の全順列を求め，しりとりになっているものを語数と併せて配列に保存
wperms = list(itertools.permutations(words, len(words)))
shiritoris = []
for wperm in wperms:
    shiritori = []
    n = 0
    while (n < len(wperm)-1 and words_ht[wperm[n]][1] == words_ht[wperm[n+1]][0]):
        n += 1
    for i in range(0, n+1):
        shiritori += [wperm[i]]

    shiritoris += [shiritori]

# しりとりの中で単語数が最大のものを出力
print(max(shiritoris))

words.txt

たぬき
ねこ
きつね
こぶた

コマンドプロンプトでの実行結果

>python shiritori.py
['ねこ', 'こぶた', 'たぬき', 'きつね']

---

1. 文字化け回避のため． ↩

2. 大きすぎてピンと来ないが，1無量大数が10の68乗であることを考えるととんでもない数である． ↩