!"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~0123456789AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZzという94種類の文字のなかから、ちょうど、16文字つかって、文字列を作ります。 以下の条件で、可能なすべての文字列を上の序列で辞書順にならべたとき 99999999999999999 番目(最初の文字列は0番目)の文字列は何か？
- a. 文字の重複を許したとき
- b. 重複を許さないとき
- c. 重複を許さない組合せのとき
準備：
(use srfi-1)
(use srfi-13)
(use gauche.sequence)
;; 基本94文字
(define *chars* "!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~0123456789AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz")
;; ターゲットとなる値
(define *value* 99999999999999999)
基本的には、基数変換の拡張で考えることができる。
なお、以下の説明では最下位桁を0桁目、その左を1桁目…で最上位桁(一番左の桁)を15桁目 と言うことにする。
これはターゲット値を94進数で表せば良いだけ。
;; weightsに与えられた基数ベクタを使ってnumを変換
(define (base-conv num weights)
(let loop ((w weights) (d '()) (n num))
(cond ((null? w) (reverse d))
(else (call-with-values (cut quotient&remainder n (car w))
(lambda (q r) (loop (cdr w) (cons q d) r)))))))
(define (base94xN ndigits num)
(base-conv num (map (cut expt 94 <>) (iota ndigits (- ndigits 1) -1))))
(define (answer-a)
(map-to <string> (cut ref *chars* <>) (base94xN 16 *value*)))
(answer-a) => "!!!!!!!;6'uVO%_e" ;; 答えは !!!!!!!;6'uVO%_e
最上位桁は94通り、次は93通り…で最下位桁は94-15=79通りの選択肢がある。 つまり、0桁目の重みは1、1桁目の重みは79 (1桁目が1増えると79増える)、 2桁目の重みは79x80、以下同様にして15桁目の重みは 79x80x81x...x93となる。
一般にN進数のd桁目の重みは N^d だが、この問題の場合はd桁目の重みが (78+d)! / 78! になっていると言える。
で、上のbase-convは重みベクタを自由に与えられるように作ってあるので、 そういう重みベクタを与えてやれば良い。
最後の文字列に変換するところでは、上位桁で使った文字を除いた文字列に 対してインデックスする。
;; 重みベクタの計算
(define (b-weights ndigits)
(let loop ((n (- ndigits 1)) (r '(1)) (k 1))
(cond ((zero? n) r)
(else (let1 kk (* k (- 94 n))
(loop (- n 1) (cons kk r) kk))))))
(define (answer-b)
(let loop ((digits (base-conv *value* (b-weights 16)))
(chars *chars*)
(r '()))
(cond ((null? digits) (list->string (reverse r)))
(else (let1 ch (ref chars (car digits))
(loop (cdr digits) (string-delete chars ch) (cons ch r)))))
))
(answer-b) => "!\"#$%&'fosI;t`Hg" ;; 答えは !"#$%&'fosI;t`Hg
今度は各桁の重みが異なるだけでなく、各桁の数値によっても重みが変化する。
規則をさぐるために、まず簡単な例から考えてみよう。 わかりやすくするために、各桁を表すのにアラビア数字を使う。 また、使う文字数をP、総桁数をDとする。 (本来の問題はP=94, D=16というわけだ)。
ちいさなP, Dに対して、全ての得られる列を順に列挙してみる。 規則性がわかりやすいように並べてある。
P=6, D=3
012 013 014 015
023 024 025
034 035
045
123 124 125
134 135
145
234 235
245
345
P=7, D=4
0123 0124 0125 0126
0134 0135 0136
0145 0146
0156
0234 0235 0236
0245 0246
0256
0345 0346
0356
0456
1234 1235 1236
1245 1246
1256
1345 1346
1356
1456
2345 2346
2356
2456
3456
ここで、次の変換 (δ変換と呼ぼう) を考える。元の数値vに対して、 δ(v)の各桁は次のように計算される。
たとえば v = 0123 だと δ(v) = 0000。v = 1246 だと δ(v) = 1011。 この変換の意味は、全ての桁を0からスタートするようにしていること。例えば P=6, D=3に変換をかけたものをもとの列と並べてみるとこうなる。 この変換は可逆であることに注意。
P=6, D=3
元の数列 変換後
012 013 014 015 000 001 002 003
023 024 025 010 011 012
034 035 020 021
045 030
123 124 125 100 101 102
134 135 110 111
145 120
234 235 200 201
245 210
345 300
δ変換後の数値に対して、d桁目の数の「重み」を求めることができる。
以下のようにσ、τ、κを定義する。
n
σ(f, n) = Σ f(i)
i=0
τ(0, n) = 1
τ(k, n) = σ(λm. τ(k-1, m), n)
κ(d) : d桁目より上に出現した数字の合計
すると、d桁目より上の桁を決めた時に、d桁目の数字がpであるような要素の数は
τ(d, P-D+1-p-κ(d))
これは、τの値と各数列を並べてみればよくわかる。 例えば、P=7, D=4の場合、 3桁目が0であるものはτ(3,4)=20個、3桁目が1であり2桁目が0 であるようなものはτ(2,3)=6個、あることがわかる。 (τ(0, n)は常に1 なので省略)。
d=3 d=2 d=1
0123 0124 0125 0126 0000 0001 0002 0003 τ(3,4)=20 τ(2,4)=10 τ(1,4)=4
0134 0135 0136 0010 0011 0012 τ(1,3)=3
0145 0146 0020 0021 τ(1,2)=2
0156 0030 τ(1,1)=1
0234 0235 0236 0100 0101 0102 τ(2,3)=6 τ(1,3)=3
0245 0246 0110 0111 τ(1,2)=2
0256 0120 τ(1,1)=1
0345 0346 0200 0201 τ(2,2)=3 τ(1,2)=2
0356 0210 τ(1,1)=1
0456 0300 τ(2,1)=1 τ(1,1)=1
1234 1235 1236 1000 1001 1002 τ(3,3)=10 τ(2,3)=6 τ(1,3)=3
1245 1246 1010 1011 τ(1,2)=2
1256 1020 τ(1,1)=1
1345 1346 1100 1101 τ(2,2)=3 τ(1,2)=2
1356 1110 τ(1,1)=1
1456 1200 τ(2,1)=1 τ(1,1)=1
2345 2346 2000 2001 τ(3,2)=4 τ(2,2)=3 τ(1,2)=2
2356 2010 τ(1,1)=1
2456 2100 τ(2,1)=1 τ(1,1)=1
3456 3000 τ(3,1)=1 τ(2,1)=1 τ(1,1)=1
ここまでわかれば、一般化した基数変換を書くことができる。
;; σとτを定義しとく。
(define (σ f n)
(apply + (list-tabulate n (lambda (i) (f (+ i 1))))))
(define (τ k n)
(if (= k 0) 1 (σ (cut τ (- k 1) <>) n)))
;; ここから、与えられた順序数numに対応するδ-数列rを求めるには
;;
;; κ = 0
;; d = D-1
;;
;; d = D-1 downto 0
;; while (num > τ(d, P-D+1-κ-i))
;; num -= τ(d, P-D+1-κ-i)
;; i += 1
;; r[d] = i
;; κ += i
(define (ord num P D)
(let outer ((num num)
(d (- D 1))
(κ 0)
(δ '()))
(if (= d 0)
(reverse (cons num δ))
(let inner ((num num)
(i 0))
(let ((n (- P D -1 κ i)))
(if (< n 1)
(error "Overflow!")
(let ((tau (τ. d n)))
(if (>= num tau)
(inner (- num tau) (+ i 1))
(outer num (- d 1) (+ κ i) (cons i δ))))))))))
;; δ変換の逆変換
(define (undelta δ)
(define (rec acc rest)
(if (null? rest)
'()
(let1 d (+ acc (car rest) 1)
(cons d (rec d (cdr rest))))))
(cons (car δ) (rec (car δ) (cdr δ))))
これで、例えば (dotimes (n 35) (print n " : " (undelta (ord n 7 4)))) とかすれば、P=7, D=4の場合について最初に挙げたような全ての組合せを 順に列挙することができる。
さてここまでくれば、求める答えは (undelta (ord *value* 94 16)) であることが わかるわけだが、上の定義だとτの計算が指数的に増えるため、 普通にやったんではえらく時間がかかる。ここはメモワイズしときましょ。
(define (τ k n)
(if (= k 0) 1 (σ (cut τ. (- k 1) <>) n)))
(define τ.
(let ((tab (make-hash-table 'equal?)))
(lambda (k n)
(or (ref tab (list k n) #f)
(let1 t (τ k n)
(set! (ref tab (list k n)) t)
t)))))
で、ファイナルアンサー。
(define (answer-c) (map-to <string> (cut ref *chars* <>) (undelta (ord *value* 94 16)))) (answer-c) => "\"%'[03569FfLoUXy"
でも本当にあってるかどうか自信ないなあ。他の人の解答求む。
組み合わせの数を使うとこんな感じ？
(let loop ((chars (string->list *chars*))
(str '())
(num *value*))
(if (= (length str) 16) (list->string (reverse str))
(let ((x (c (- (length chars) 1) (- 15 (length str)))))
(if (> x num) (loop (cdr chars) (cons (car chars) str) num)
(loop (cdr chars) str (- num x))))))
=> "\"%'[03569FfLoUXy"
fが文字列上の位置に直す手続き。 gがパターン数を計算する手続き。 hがP個の中からn番目のものを取ったときに次に何個の中から取ればいいか計算する手続き。
(define (hoge f g h num P D)
(let loop ((num num) (P P) (D D) (n 0) (r '()))
(if (zero? D) (list->string (map (lambda (x) (string-ref *chars* x))
(f (reverse r))))
(let ((x (g (h P n) (- D 1))))
(if (> x num) (loop num (h P n) (- D 1) 0 (cons n r))
(loop (- num x) P D (+ n 1) r))))))
(hoge (lambda (x) x) expt (lambda (x n) x) *value* 94 16)
(hoge (lambda (x) (let loop ((x x) (r '()))
(if (null? x) (reverse r)
(loop (map (lambda (y) (if (> (car x) y) y (+ y 1)))
(cdr x))
(cons (car x) r)))))
(lambda (x y) (/ (factorial x) (factorial (- x y))))
(lambda (x y) (- x 1))
*value* 94 16)
(hoge (lambda (x) (let loop ((x x) (n 0) (r '()))
(if (null? x) (reverse r)
(loop (cdr x) (+ n (car x) 1)
(cons (+ n (car x)) r)))))
(lambda (x y) (/ (factorial x) (factorial y) (factorial (- x y))))
(lambda (x y) (- x y 1))
*value* 94 16)
全パターン数を計算するexpt,(lambda (x y) (/ (factorial x) (factorial (- x y)))),(lambda (x y) (/ (factorial x) (factorial y) (factorial (- x y))))からhogeに渡している他の関数を導き出せそうだけど、今のところ思いつかない。
Tag: Puzzle