辞書式配列(辞書式順序)

スポンサーリンク
a,\ b,\ c,\ d,\ eの5文字を1個ずつ使ってできるすべての文字列をアルファ ベット順に並べる.  dbeac\ は何番目にあるか.   \ 88番目は何か. アルファベットがわかりづらい人は,\ このように数字に置き換えてしまえばよい. {最高位を小さい数字から順に固定し,\ それぞれ何通りあるかを求めていく.} 最高位が1の数は,\ 残りの4数を下4桁に並べるから,\ 4!=24通りある. よって,\ 最高位が1の数を全て並べると,\ {最後の数15432が24番目}だとわかる. そして,\ 最高位が2の数は25番目から始まる.\ つまり,\ 21345が25番目. 同様に考えると,\ 最高位が3の最後の数35421は243=72番目である. 目標は42513なので,\ 最高位が4になるここからは{千の位も固定して考えていく.} 41○○○となる数が6通りあり,\ ここまでで72+6=78番目が終わる. つまり,\ 42○○○が79番目から始まる. ここまで来れば,\ {後は順に書き出す}ほうが手っ取り早い. 421○○,\ 423○○,\ 425○○の順で書き出せば,\ 42○○○の5番目だとわかる. $$ 88番目は43251,\ つまり\ dcbea}\ である.} 同様に,\ {最高位を小さい数字から順に固定し,\ それぞれ何通りあるかを考える.} 3○○○○の最後の数は\ 243=72\ 番目である. また,\ {4○○○○の最後の数は\ 244=96\ 番目}である. よって,\ {88番目は最高位が4の数}であるとわかる. 千の位も固定し,\ さらに絞り込んでいく. {42○○○の最後の数は,\ 72+6+6=84\ 番目}である. {43○○○の最後の数は84+6=90\ 番目}となり,\ 88を超える. よって,\ 求める数が43○○○とわかり,\ 84+4=88より,\ 順に4個書き出す. 間違えない自信があるならば,\ 90番目から戻るほうが速い. 最後,\ 忘れずにアルファベットに戻して答える.
タイトルとURLをコピーしました