Archive for 2015年8月|Monthly archive page

projecteuler24

 projecteuler問題24は、辞書的順列問題。0 から 9 までの数字を組み合わせた10桁の数値を辞書的に並べ、百万番目を求めるもの。
 当然一番目は 0123456789 。先頭が 0 である数は

 9! = 362880 個。

 とすれば、

1000000 - 2*362880 = 274240

 となり、解答は先頭が 2 の 274240 番目。
 こんな風に各桁を求めれば、解答に行く着くはず。
 これを関数にすれば

(define (make-ans cnt lst, (res '()))
  (-- cnt)
  (while (> cnt 0)
    (let (cm (apply * (sequence 1 (-- (length lst)))))
      (push (pop lst (/ cnt cm)) res -1)
      (setq cnt (% cnt cm))))
  (apply string (if lst (append res lst) res)))

 実際に試すと、

> (make-ans 1 (sequence 0 9))
"0123456789"
> (make-ans 362880 (sequence 0 9))
"0987654321"
> (make-ans 362881 (sequence 0 9))
"1023456789"
> (make-ans 1000000 (sequence 0 9))
"2783915460"
> 

 こんな感じ。
 ちなみ、例題にある 0 から 2 の三桁も

> (map (hayashi make-ans (sequence 0 2)) '(1 2 3 4 5 6))
("012" "021" "102" "120" "201" "210")
> (map (fn (x) (make-ans x (sequence 0 2))) '(1 2 3 4 5 6))
("012" "021" "102" "120" "201" "210")
> 

 この通り。
 hayashi は拙作の関数で二番目以降の引数を curry のように扱える関数で、newlisp-utility.lsp に置いてあります。
 以上、如何でしょうか?

広告