Y箱

実際に数列を作るときに、樹形図を描いたのですが、それを見ていて思いつい た方法です。

図を作りました。 。

樹形図を描いてX番目の数を求めるときには、全部描いて、端から数えればい いわけですが、図のようにあるノードの下にある葉の数は計算で求めることが できるので、労力を減らせます。

図は、0-3の4つの数で、4ケタの数を作るときの図です。このとき全体では、 4!=24通りありますが、この15番目の数が何であるか考えます。

1桁目の数は0,1,2,3のいずれかですが、それぞれで始まる数は3!=6つあります。 求めるのは15番目ですから、0と1の下には無いことがわかります。1桁目の数は、2で決まり です。さて、残りは15-(6*2)=3こです。2の次の数は、0,1,3のいずれかですが、 それぞれの下には、2!=2こずつの数があります。残りは3こなので、2番目 の数は、1で決まりです。のこりの数は、0,3で残り1こなので、最後は03となり ます。 答は、2103 です。

さて、これを実装しようとしたのが、下のコードです。最初に解いた時のもの を1.4に対応させたり、ベタで書いてあった階乗のところを関数化したりなど ちょっときれいにしてあります。 あと、最後の詰めのところをごにょごにょしてあって、ちょっと気に入りませ ん。うまい方法が無いか考えてみます。