Problem24

Scheme 30分プログラム

30分プログラム、その295。Problem24 via Project Euler。

順列とはモノの順番付きの並びのことである. たとえば, 3124は数1, 2, 3, 4の一つの順列である. すべての順列を数の大小でまたは辞書式に並べたものを辞書順と呼ぶ. 0と1と2の順列を辞書順に並べると

012 021 102 120 201 210

になる.

0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目を答えよ

最初はutil.combinationsを使っていたけれど、さすがに遅すぎるので、工夫してみた。
まず、0ABCDEFHIGのように最初が0で始まる数字は9!個存在している。同様に、01BCDEFHIGのような最初が01の数字は8!個ある。
これを使うと、実際に組み合せを計算せずに、n番目を計算することができる。

使い方

$ time gosh problem24.scm
2783915460
gosh problem24.scm  0.06s user 0.03s system 49% cpu 0.182 total

ソースコード

#! /opt/local/bin/gosh
;; -*- mode:scheme; coding:utf-8 -*-
;;
;; problem24.scm -
;;
;; Copyright(C) 2008 by mzp
;; Author: MIZUNO Hiroki / mzpppp at gmail dot com
;; http://howdyworld.org
;;
;; Timestamp: 2008/04/30 21:28:42
;;
;; This program is free software; you can redistribute it and/or
;; modify it under MIT Lincence.
;;

;;(use util.combinations)
;;(use srfi-1)
;; (define n 0)
;; (print 
;;  (call/cc (lambda (break)
;; 	    (permutations-for-each
;; 	     (lambda (x) 
;; 	       (print n " " x)
;; 	       (set! n (+ n 1))
;; 	       (if (= n 1000000)
;; 		   (break x)))
;; 	     (iota 10)))))

(use srfi-1)
(use util.match)
(define (fact n)
  (if (= n 0)
      1
      (* n (fact (- n 1)))))
(define (make-facts n)
  (reverse (map fact (iota (- n 1) 1))))

(define (change n facts)
  (match facts
    [() '()]
    [(x . xs) 
     (if (>= n x)
	 (match-let1 (y . ys) (change (- n x) facts)
	   (cons (+ y 1) ys))
	 (cons 0
	       (change n (cdr facts))))]))

(define (order->number lst numbers)
  (match lst
    [() numbers]
    [(x . xs) 
     (let1 n (list-ref numbers x)
       (cons n (order->number xs (delete n numbers))))]))

(define (solve x y)
  (string-join 
   (map x->string
	(order->number 
	 (change x (make-facts y)) (iota y))) ""))

(print (solve (- 1000000 1) 10))

参考