#本記事について
**「あれ」**とはこれである。
「GAKKOUの6文字を並び替えてできる360個の文字列を辞書式に並べるとき、100番目の文字列を求めよ」
駿台予備校が大学入学共通テスト試験前に出した広告、そこにぽつんと記載の合った問題である。
この問題は数Aをしっかり勉強していればそこまで難しくない。
ここまでしっかり勉強してきた受験生なら電車の待ち時間にノートを広げて計算すれば解けるだろう。
そうして計算した結果出てくる答えが絶妙で、受験生に感動とエールを送る素晴らしい問題とSNSで非常に話題になった。
本記事はそんな受験生の涙ぐましい努力をコンピューターという圧倒的計算能力で無に帰すというものである。
上記リンクに解き方も書いていたので見てみよう。
・ABCD…のアルファベット順でGAKKOUを置き換えます。Aは最初（1番目）だから1、BCDEFがないのでGは2番目、そう考えるとKは3、Oは4、Uは5となり、GAKKOUは213345と表せます。
・A（1）で始まる6桁を考えます。A（1）以下の組み合わせは、5×4×3×2×1＝120ですが、Kが二つあるので、120を2で割って60。これがA（1）で始まる文字列の数です
・同じようにG（2）で始まる6桁を考えます。G（2）以下の組み合わせは、5×4×3×2×1＝120ですが、Kが二つあるので、120を2で割って60。これがG（2）で始まる文字列の数ですが、A（1）で始まる分を合わせると、120になってしまい100を超えてしまいます。
・少し戻って最初はG（2）、次はA（1）で始まる6桁を考えます。組み合わせは4×3×2×1＝24ですが、やはりKが二つあるので、24を2で割って12。これがG（2）、A（1）で始まる文字列の数です。
・同じように最初はG（2）、次はK（3）で始まる6桁を考えます。組み合わせは4×3×2×1＝24ですが、今回はKはひとつ使っているので割る必要はありません。24がG（2）、K（3）で始まる文字列の数です。
・これまでの計算で分かった60、12、24を足すと、96通りまで見えてきました。23（GK）で始まり、最も大きい数、235431が96番目です。
・97番目以降は24（GO）で始まる数を考えます。241335が97番目、241353が98番目、241533が99番目…ゴールが見えてきました。
人類は無力である。
たかだか360個しかない文字列の計算にすらこんな手順を踏まねばならない。
たかだか360個程度の文字列など全て列挙して数えてしまえば良い。
#プログラミングしてみよう
というわけでこの問題をプログラミングでどのように解くか、説明していきます。
言語はpythonを使います。
あまりpythonを使ったことがない人でもわかるよう丁寧に説明していきます。
pythonはGoogle Colaboratoryというサービスを使えばブラウザだけで使う事ができます。
一緒にやってみましょう。
まずは上記リンクからGoogle Colaboratoryにアクセスし、コードを書く部分を出します。
上部に「+コード」と書かれた部分がありますね？そこをクリックすると以下のようにコード記載部が出てきます。
試しにこの部分へ以下のコードを書いてみましょう。コピペでも構いません。
print("Hello World!")
書けたら▶マークを押して実行します。
しばらく待つと以下のようになります。
下部分に「Hello World!」という文字が現れました。
これは printというコマンドで「Hello World!」という文字列を出力した ということです。
「Hello World!」の部分をてきとうに変えてみると対応した文字が出力されます。
では問題に移りましょう。
「GAKKOUの6文字を並び替えてできる360個の文字列を辞書式に並べるとき、100番目の文字列を求めよ」
解き方の方針としては以下になります。
①「GAKKOU」を変数へ格納
②「GAKKOU」の6文字を並び替えてできる360個の文字列を全て作る
③辞書順に並び替える
④100番目を確認する
ここからはプログラミングをあまりしたことがない人にとって難しいと感じる部分があるかもしれませんが、**「書いて実行します」**と書いた部分はコピペでいいので実際にコードを実行しながら読んでみてください。
##①「GAKKOU」を変数へ格納
まず「GAKKOU」の文字列を変数へ格納します。
変数とは値を記録しておく箱のようなものです。
書き方は以下です。
変数名="文字列"
S="GAKKOU"
これで「S」という変数に「GAKKOU」という文字が入りました。
試しにSの1文字目を確認してみましょう。
pythonでは先頭を0文字目、次を1文字目、...と数えますから、Sの1文字目は「GAKKOU」の2つ目、つまり「A」になるはずです。
Sの1文字目はS[1]と書きます。
S="GAKKOU"
print(S[1])
【実行結果】
A
##②GAKKOUの6文字を並び替えてできる360個の文字列を全て作る
まず並び替えて作る文字列を格納する変数を用意しましょう。
普通の変数には値が一つしか入らないので、値がたくさん入る「セット」というものを使います。
セットの作り方は以下です。
セットの名前=set()
名前をS_setとすると以下のようになります。
S_set=set()
次に6文字を並び替えてできる文字をセットに追加していきます。
ここはかなり難しいのでわからなければコピペでもかまいません。
6文字の並び替えは「Sの0文字目」「Sの1文字目」...「Sの5文字目」をいろいろな順番で取ってくることでできます。
S="GAKKOU"ですから
S[0]+S[1]+S[2]+S[3]+S[4]+S[5]="G"+"A"+"K"+"K"+"O"+"U"="GAKKOU"
S[0]+S[1]+S[2]+S[3]+S[5]+S[4]="G"+"A"+"K"+"K"+"U"+"O"="GAKKUO"
S[0]+S[1]+S[2]+S[4]+S[3]+S[5]="G"+"A"+"K"+"O"+"K"+"U"="GAKOKU"
...
S[5]+S[4]+S[3]+S[2]+S[1]+S[0]="U"+"O"+"K"+"K"+"A"+"G"="UOKKAG"
と作っていけばよいわけです。
これを作るのにitertoolというものを使います。
上記のような順列をいい感じに作ってくれるシステムです。(ライブラリと言います)
試しに以下を実行してみてください
import itertools
for p in itertools.permutations(range(6)):
print(p)
【実行結果】
(0, 1, 2, 3, 4, 5)
(0, 1, 2, 3, 5, 4)
(0, 1, 2, 4, 3, 5)
...
(5, 4, 3, 2, 1, 0)
このようにいい感じに順列を作ってくれるのがitertoolsです。
あとはこれを使って並び替えた文字を作っていきます。
以下を書いて実行してみましょう。
import itertools
for p in itertools.permutations(range(6)):
T=S[p[0]]+S[p[1]]+S[p[2]]+S[p[3]]+S[p[4]]+S[p[5]]
print(T)
【実行結果】
GAKKOU
GAKKUO
GAKOKU
...
UOKKAG
いい感じに「GAKKOU」の並び替えが出来ました。
上記のコードは以下を行っています。
T=S[0]+S[1]+S[2]+S[3]+S[4]+S[5]="G"+"A"+"K"+"K"+"O"+"U"="GAKKOU"
T=S[0]+S[1]+S[2]+S[3]+S[5]+S[4]="G"+"A"+"K"+"K"+"U"+"O"="GAKKUO"
T=S[0]+S[1]+S[2]+S[4]+S[3]+S[5]="G"+"A"+"K"+"O"+"K"+"U"="GAKOKU"
...
T=S[5]+S[4]+S[3]+S[2]+S[1]+S[0]="U"+"O"+"K"+"K"+"A"+"G"="UOKKAG"
作った文字列は「T」という変数に格納し、それを出力しているわけです。
「T」を先程作ったセットへ格納していきます。
セットへの格納は以下のように書きます。
セット.add(格納するもの)
S_set.add(T)
セットもprintで出力できます。
ここまでをまとめた以下のコードを実行してみましょう。
S="GAKKOU"
S_set=set()
import itertools
for p in itertools.permutations(range(6)):
T=S[p[0]]+S[p[1]]+S[p[2]]+S[p[3]]+S[p[4]]+S[p[5]]
S_set.add(T)
print(S_set)
【実行結果】
{'UKAGOK', 'UGKOAK', 'AUKOKG',...,'UKOGAK'}
「GAKKOU」の文字列を並び替えたものがちゃんとセットに入っているのがわかります。
ところで「GAKKOU」はKが重複しているので二重で追加されている文字があるのでは？と心配になりますね。
しかしセットは重複したものが追加できないのでその心配はありません。
すでに入っている文字列を追加しようとしても無視されます。
##③辞書順に並び替える
②まででセットへ文字列を追加することができました。次に並び替えを行います。
しかし実はセットは並び替えができません。
そこで並び替えのできる「リスト」を使います。
まずセット→リストへ変換を行います。
書き方は以下です。
list(セット)
S_list=list(S_set)
そうしてリストの要素を辞書順に並び替えします。
並び替えの書き方は以下です
リスト名.sort()
S_list.sort()
ここまでの操作の後、リストを出力してみましょう。
S="GAKKOU"
S_set=set()
import itertools
for p in itertools.permutations(range(6)):
T=S[p[0]]+S[p[1]]+S[p[2]]+S[p[3]]+S[p[4]]+S[p[5]]
S_set.add(T)
S_list=list(S_set)
S_list.sort()
print(S_list)
【出力結果】
['AGKKOU', 'AGKKUO', 'AGKOKU',...,'UOKKGA']
いい感じに辞書順に並んでいますね。答えまで後少しです。
##④100番目を確認する
あとは辞書順に並び替えたリストの100番目を確認するだけです。
ただし、リストも文字列同様に先頭の要素が0番目、次が1番目、...と数えますので、100番目はひとつずれてS_list[99]となります。
ここまでの手順全てを合わせたのが以下のコードです。
さあ、答えを確認しましょう。
S="GAKKOU"
S_set=set()
import itertools
for p in itertools.permutations(range(6)):
T=S[p[0]]+S[p[1]]+S[p[2]]+S[p[3]]+S[p[4]]+S[p[5]]
S_set.add(T)
S_list=list(S_set)
S_list.sort()
print(S_list[99])
#受験生の皆さんへ
大学入学共通テスト終わった方、お疲れ様でした。
追試や二次試験を受けられる方はあとちょっと、体調に気をつけて頑張ってください。