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

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

- [最長しりとりを求めるプログラムを今更ながらに作ってみた - Qiita](https://qiita.com/YSRKEN/items/543938ba6a0fcb46e38d)

# 詳細
語群は `words.txt` に保存しておく．このとき，文字コードは **Shift JIS** とする[^2]．

```:words.txt
ごりら
りんご
ぱんだ
らっぱ
```
[^2]: 文字化け回避のため．

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

```ruby:shiritori.rb
# 語群を配列に保存
words = readlines(chomp: true)
p words
```

```:コマンドプロンプトでの実行結果
>type words.txt | ruby shiritori.rb
["ごりら", "りんご", "ぱんだ", "らっぱ"]
```

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

```ruby: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: 語群の全順列を求め，しりとりになっているものを語数と併せてハッシュに保存する

```ruby: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: しりとりの中で単語数が最大のものを出力する

```ruby: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匹で計算するとなれば

```math
\log_{10}151!\fallingdotseq264.94
```

より計算量は $10^{264.94}\fallingdotseq8.7\times10^{264}$ 以上[^1]となる．
[^1]: 大きすぎてピンと来ないが，1無量大数が10の68乗であることを考えるととんでもない数である．

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

```py: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
['ねこ', 'こぶた', 'たぬき', 'きつね']
```