辞書式順序(何番目の数か)

方針

解答

⓪ 発想 — どう考え始めるか。 「何番目か」は、$1$ つずつ数えていては終わらない。

先頭の数字を決めると、残り $4$ 桁の並びが $4!$ 個のかたまりになる。このブロック単位で数を積み上げる。

逆に「$80$ 番目は?」も、同じブロック割りで上の位から絞り込める。

辞書式は、ブロックの大きさで位取りをする。この見方が主役だ。

5個の数字の順列は $5!=120$ 個。先頭の数字を1つ決めると、残り4桁の並びが $4!=24$ 個あるので、「先頭が◯の整数」は24個ずつのかたまりになる。

(1) 51234 の順位

先頭が 1, 2, 3, 4 の整数は、それぞれ24個ずつで合計 $4\times 24=96$ 個あり、これらは全部 51234 より小さい(先頭が5より小さいから)。

次に先頭が5の整数を考える。51234 は、先頭5の後ろが「1234」で、これは残り4個 $\{1,2,3,4\}$ を小さい順に並べたいちばん小さい並びだ。だから先頭5のかたまりの中では1番目。

$$96+1=97(\text{番目})$$

(2) 80番目の数

80番目がどの『先頭』のかたまりに入るかを調べる。24個ずつなので

• 先頭1: 1〜24番目、先頭2: 25〜48番目、先頭3: 49〜72番目、先頭4: 73〜96番目

80番目は先頭4のかたまりの中の $80-72=8$ 番目だ。先頭は4に決まる。

残る数字は $\{1,2,3,5\}$。2桁目を決めると残り3桁が $3!=6$ 個ずつのかたまりになる。$\{1,2,3,5\}$ を小さい順に見て

• 2桁目1: 1〜6番目、2桁目2: 7〜12番目

8番目は2桁目2のかたまりの $8-6=2$ 番目。2桁目は2。

残る数字は $\{1,3,5\}$。3桁目を決めると残り2桁が $2!=2$ 個ずつ。

• 3桁目1: 1〜2番目

2番目はこの中にあり、3桁目は1、その中の2番目。残る $\{3,5\}$ の並びは小さい順に「35」(1番目)、「53」(2番目)だから、下2桁は53。

つなげて

$$4,2,1,5,3⟹42153$$

発展 — 一歩先へ。 辞書式の順番が決まると、ある並びの「次の並び」を、全部を作り直さずに求められる。

手順はこうだ。右から見て、初めて増加する箇所を探す。そこの数字を、右側にあるより大きい数字のうち最小のものと入れ替え、さらに右側を小さい順に並べ替える。これで辞書式のちょうど $1$ つ後ろが得られる。

この「次の順列」の作り方は、コンピュータで順列を辞書順にもれなく生成するときの土台になっている。$120$ 個の並びを $1$ 番から順に吐き出したり、ある並びから何番か先へ飛んだりできる。数え上げと手順(アルゴリズム)は地続きだ。

別解

別解 — 順位を「階乗進法」の数として読む(得意な人向けの高い視点)。 位取りのかたまりが $4!,3!,2!,1!$ だったことに注目すると、順位そのものを「位の重みが階乗になった数」として読める。

まず順位を $0$ から数え直す(最小の $12345$ を $0$ 番目とする)。ある並びの $0$ 始まりの順位は、各桁について「その桁より右にある、自分より小さい数字の個数」を、重み $4!,3!,2!,1!$ でかけて足した値になる。

(1) $51234$ では、先頭 $5$ の右に小さい数字が $4$ 個あり、以降の桁は右に自分より小さい数字が $1$ つもない。だから $0$ 始まりの順位は $4\times 4!+0\times 3!+0\times 2!+0\times 1!=96$。$1$ 始まりに直して $97$ 番目。

(2) $80$ 番目は $0$ 始まりで $79$。これを階乗の重みで割り分ける。$79=3\times 4!+1\times 3!+0\times 2!+1\times 1!$ で、係数は上の桁から $(3,1,0,1)$、最後の桁は残り $1$ 個で自動的に決まる。この係数は「残っている数字のうち、下から何個を飛ばして次を取るか」を表す。$\{1,2,3,4,5\}$ から $3$ 個飛ばして $4$、残り $\{1,2,3,5\}$ から $1$ 個飛ばして $2$、残り $\{1,3,5\}$ から $0$ 個飛ばして $1$、残り $\{3,5\}$ から $1$ 個飛ばして $5$、最後は $3$。よって $42153$。

順位と並びを「位の重みが $10,100$ でなく $4!,3!,2!$ の数」で橋渡しするこの見方なら、順位を $1$ つの数として分解するだけで並びが定まる。本解の積み上げと同じ $97$ 番目・$42153$ にたどり着く。