「GAKKOU」問題を Python で解いてみよう

2022年1月19日 2023年11月8日

カテゴリ: プログラミング

Python

電車の広告で
「GAKKOU という 6 文字を並び替えてできる 360 個の文字列のうち、辞書式に並べて 100 番目にくるものは何か？」
という問題がとても感動的だと話題になっているそうですね。

この問題を解くには数学の知識が必要で、それなりの時間を要するでしょう。
そんな問題でも Python ならたった 2 行で簡単に解くことができます。

こうです。

import itertools
print("".join(sorted(list(set(itertools.permutations("GAKKOU"))))[99]))

GAKKOU(学校)からGOUKAKU(合格)が導き出せましたね。
アナグラムとしても素晴らしいですが、すべての組み合わせを並べた 100 番目というキリの良さも美しいですね。

上記の例では、Python の凄さを表現するために無理やり 2 行にまとめてみましたがとっても読みづらいかと思います。
解説を交えながら、もう少しお行儀のいい(読みやすい)コードを紹介していきます。

ある文字列を並び替えてできるすべての文字列の組み合わせを求める

文字列の要素の並び方の組み合わせを取得するには itertools モジュールの permutations 関数を使用します。

import itertools
text = "GAKKOU"
p = itertools.permutations(text)

ここで変数 p は itertools.permutations object というイテレータで、そのままでは中身を参照できないので一旦 list に変換してみましょう。

l = list(p)
print(len(l)) # 720

変数 l の要素数を見ると 720 となるはずです。
問題文では「360 個の文字列」とあるので組み合わせ数が 2 倍になってしまいました。

これは「K」をふたつ使っていて、それぞれ別の文字として組み合わせを作っているからなのです。

重複を削除するためには、一旦 set に変換するのが手っ取り早いです。

s = set(l)
print(len(s)) # 360

これで問題文と同じ個数になりましたね。

「辞書式に並べて」の部分を解決するには sorted 関数でソートするだけで大丈夫です。
ただし、set のままだとソートできないので list に変換します。

l = sorted(list(s))

100 番目の要素の要素番号は 99 です。

print(l[99]) # ('G', 'O', 'K', 'A', 'K', 'U')

以上を踏まえて、読みやすいプログラムにまとめると次のようになります。

import itertools
text = "GAKKOU"

p_list = sorted(list(set(itertools.permutations(text))))
message = "".join(p_list[99])

print(message)