Y箱

これもファレイ数列の問題です。

数えるだけなので、他にいい方法もありそうですが、70の方法で正面から解いてます。

ところが、初めに作ったものは再帰で実装して作ったデータを全部持っていたため。OutOfMemoryになってしまった
で、今ちょうど読んでいる、Joy of Clojureで、遅延評価のクイックソートのことが出ていたので、それを使ったらできた。
ついでにJoCに出ていた、名前付き引数を使ってデータ定義をしなくてもいいようにしてみたけれど、あまりよくないかな。







結局、ファレイ数列を生成する関数を作ればいいのです。ある2つの分数があったとき、その間のすべての対象を求めるわけです。
こんな感じ。

1)分数をa/bとc/dでa/b < c/dとします。
2)空の結果リストと待ちスタックを作ります。
3)中間数Xを求めます。
  (a+c)/(b+d)
4)求めたXと分母の最大値を比べて
  4-1) Xの分母が分母の最大値より大きい場合、a/bの右にはc/dしか無いので、a/bを結果リストに入れて、待ちスタックの最初の数Yを取り出し、c/dとYで3)に戻ります。
     4-1-1) 待ちスタックが空だったら、c/dを結果リストに入れて、結果リストを返す。
  4-2) Xの分母が分母の最大値以下の場合、c/dを待ちスタックに入れて、a/bとXで3)に戻ります。

この手順で分母が4以下のファレイ数列を作ってみます。
0/1と1/1で始めます。

a/b c/d X    結果                 待ち
0/1 1/1 1/2                                4-2パターン
                                  1/1
0/1 1/2 1/3                                4-2パターン
                                  1/2 1/1
0/1 1/3 1/4                                4-2パターン
                                  1/3 1/2 1/1
0/1 1/4 1/5                                4-1パターン
             0/1                  1/2 1/1
1/4 1/3 2/7                                4-1パターン
             0/1 1/4              1/1
1/3 1/2 2/5                                4-1パターン
             0/1 1/5 1/3        
1/2 1/1 2/3                                4-2パターン
             0/1 1/5 1/3          1/1
1/2 2/3 3/5                                4-1パターン
             0/1 1/5 1/3 1/2
2/3 1/1 3/4                                4-2パターン
             0/1 1/5 1/3 1/2      1/1
2/3 3/4 5/7                                 4-1パターン
             0/1 1/5 1/3 1/2 2/3
3/4 1/1 4/5                                 4-1パターン
             0/1 1/5 1/3 1/2 2/3 3/4
=> 0/1 1/5 1/3 1/2 2/3 3/4 1/1

- my-numerator
- my-denominator
- frac-reduce
- farey-mediant
 前の問題などで使った関数

遅延評価のやつ。
- farey-list
 計算用のデータの定義。
  [a/b] [c/d] [待ちスタック]
  [[0 1] [1 1] nil] にすると、ファレイ数列が全部出ます。

- pe-73
 ロジックを実装したもの。ただ、遅延評価になっているので、結果リストは吐き出されるだけで、データとしては保持していない。

遅延評価なので、1000000でも、10こくらいならすぐに答が返ります。

user> (take 10 (farey-seq 1000000))
([0 1] [1 1000000] [1 999999] [1 999998] [1 999997] [1 999996] [1 999995] [1 999994] [1 999993] [1 999992])

名前付き引数のやつ
- farey-seq
  ロジックは同じ。
  引数に最大値だけ与えると、ファレイ数列を返します。

user> (farey-seq 5)
([0 1] [1 5] [1 4] [1 3] [2 5] [1 2] [3 5] [2 3] [3 4] [4 5] [1 1])

  両端を与えると、その間だけ返します。

user> (farey-seq 5 :start [1 3] :end [1 2])
([1 3] [2 5] [1 2])

  へんなところだとできませんけど

user> (farey-seq 5 :start [1 3] :end [3 4])
([1 3] [3 4])

- pe-73
  farey-seqを使って解く関数