ypsilon-takai/description.md

## description.md

      
    Raw
  

              description.md
            
          
    解説

実際に数列を作るときに、樹形図を描いたのですが、それを見ていて思いつい
た方法です。
図を作りました。
。
樹形図を描いて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に対応させたり、ベタで書いてあった階乗のところを関数化したりなど
ちょっときれいにしてあります。
あと、最後の詰めのところをごにょごにょしてあって、ちょっと気に入りませ
ん。うまい方法が無いか考えてみます。

  
## pe_24_1.clj
;; Problem 24  : 2011/5/10
;; "Elapsed time: 1.543492 msecs"

(defn factrial-list [n]
  (reductions * (range 1 n)))

(loop [num-list [0 1 2 3 4 5 6 7 8 9]
       f-list (reverse (factrial-list (count num-list)))
       remains (dec 1000000)
       res-list []]
  (if (empty? f-list)
    (conj res-list (first num-list))
    (let [div (quot remains (first f-list))
          tgt-num (nth num-list div)]
      (recur (remove #(= % tgt-num) num-list)
             (rest f-list)
             (rem remains (first f-list))
             (conj res-list tgt-num )))))
	;; Problem 24 : 2011/5/10
	;; "Elapsed time: 1.543492 msecs"

	(defn factrial-list [n]
	(reductions * (range 1 n)))

	(loop [num-list [0 1 2 3 4 5 6 7 8 9]
	f-list (reverse (factrial-list (count num-list)))
	remains (dec 1000000)
	res-list []]
	(if (empty? f-list)
	(conj res-list (first num-list))
	(let [div (quot remains (first f-list))
	tgt-num (nth num-list div)]
	(recur (remove #(= % tgt-num) num-list)
	(rest f-list)
	(rem remains (first f-list))
	(conj res-list tgt-num )))))