辞書順の問題の解法

辞書順に並べて何番目かを求める問題です。

基本問題

(1)ANSUを並び替えたものを辞書順に並べたとき、NASUは何番目か
(2)AEKNNSUを並び替えたものを辞書順に並べたとき、1192番目の文字列は何か

解き方

辞書なので頭の文字から順々に数を計上していきます。
番目から文字列を求めるときも辞書順に何は何番目から何番目までを求めていきます。

解説

(1)ANSUを並び替えたものを辞書順に並べたとき、NASUは何番目か
Aが先頭の文字列は何通り作れるでしょうか。
2文字目は3通り、3文字目は2通りですね。
3\times 2=6通りになります。

Aの次はNですね。
NASUはNが頭の最初の文字ですね。
従って7番目になります。

(2)AEKNNSUを並び替えたものを辞書順に並べたとき、番目は何か
Aが先頭の文字列は何通り作れるでしょうか。
今回はNがダブっていますね。
このときは、N_1,N_2と別の文字として考えて、後で同じものとみなおせばよかったですね。
良ければ場合の数の問題の解法もご参照ください。
6文字を並べる通り数が6!=720
N_1,N_2を同じものとみなおすので720\div 2=360
Aが先頭の文字列は360通り作れます
つまりEが先頭の文字列は361番目から始まりますね。

EはAと条件は同じ(Nだけダブル)なので、Eが先頭も360通りあって、720番目までがEで始まる文字列になります。
Kも同様で721番目から始まり360通りあって、1080番目までがKで始まる文字列になります。
近づいてきました。
先頭はNになりそうですね。

Nが先頭のとき残る文字はAEKNSUです。
Nが先頭でしょうから、2文字目以降を同じように何通りあるか計上していきます
NAが先頭のとき、残る文字列はEKNSUです。
5文字ですから5!=120通りあります。
NAは1081~1200番目までになります。
この中にありそうですね。

NAEが先頭のとき、残る文字列はKNSUです。
4文字ですから4!=24通りあります。
NAEは1081~1104番目までになります。
NAKは1105~1148番目までになります。
NANは1149~1172番目までになります。
NASは1173~1196番目までになります。
この中にありそうですね。
なんとなくわかってきましたね。

NASが先頭のとき、残る文字列はEKNUです。
NASEが先頭のとき、残る文字列はKNUです。
3文字ですから3!=6通りあります。
NASEは1173~1178番目までになります。
NASKは1179~1184番目までになります。
NASNは1185~1190番目までになります。
NASUは1191~1196番目までになります。
この中にありそうですね。
もう大体わかりましたね。

NASUが先頭のとき、残る文字列はEKNです。
ここまで来たら辞書順に並べてしまいましょう。
1191がNASUEKN
1192がNASUKEN
という事で、1192番目の数は「NASUKEN」になります。

終わりに

地道な作業ですが少しずつ計上していけばいつかたどり着きます。
NASUKENが源氏に縁があるとは知りませんでした。

関連

正の約数の個数の問題の解法
数字を並べて数を作る問題の解法
円順列の問題の解法
数珠順列の問題の解法
場合の数の問題の解法(中学数学)

  • このエントリーをはてなブックマークに追加
  • Evernoteに保存Evernoteに保存