Scheme:数遊び:n番目の文字列

Scheme:数遊び:n番目の文字列

n 番目の文字列

算譜の記2004-12-04より:

!"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~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

More ...