Project Eulerの31問と同じような動的計画法を使ったナップサック問題の解き方。 m kgまで入るカバンと、n個のモノがある。 モノiはx-i kgでy-i円の価値がある。 カバンに入り、価値の合計が最大になるモノの組み合わせは何か。 まずはデータ構造の定義。 (d…

ソート selection sort insertion sort bubble sort 1/ 2/ 3 merge sort 1 2 quick sort bucket sort radix sort

Radix Sortとも。 バケツソートのバケツ数を制限して、そのかわり複数回走らせることで すでにバケツソートを書いたので実装は比較的楽。 (defn radix-sort [xs] (let [bucket-count 100 buckets (into [] (repeat bucket-count [])) max-item (apply max xs…

自動文章生成の手法の一つとして昔から有名なのが、マルコフ連鎖でn-gramから次の単語を確率的に決めて行くやり方である。 元となる文章データから、n語の連なり（prefixと呼ばれる）の後に来る単語の確率分布を作る。 起点としてn語を用意し、確率分布に従…

正の整数のシーケンスxsをO(n+m)時間でソートする方法としてBucket Sortがある。 0からxsの最大値mまで番号が付けられているvector of vectorを作成して、xsの全要素を一つずつ対応するvectorに入れていく。あとはconcatするだけ。 (defn bucket-sort [xs] (…

あやぴーさんのご指摘を参考に、バブルソートをいろいろ（主に名前を）いじってみる。 最終的にはremainingのdestructuringを後に遅らせた方が、実際に使うところの近くで定義されるのでわかりやすいんじゃないか、ということに。 (def max-min (juxt max mi…

前回からの続き。

そういえばClojureのsequenceはvectorじゃない場合は大抵countがO(n)だった。 bubble-sortでO(n)回bubbleを呼び、bubble内でO(n)回再帰して、その中でO(1)の作業だったはずが、(cond (>= i (count xs)))でもう一回O(n)の作業を入れていたのでO(n3)になる。 …

とりあえず書きなぐったもの。 (defn bubble [xs i] (loop [left [] x1 (first xs) [x2 & right :as xs] (rest xs)] (cond (>= i (count xs)) (doall (concat left [x1] xs)) :else (let [[maxx minx] ((juxt max min) x1 x2)] (recur (conj left minx) maxx…

例によってソート実装。これは面白かった。 とりあえず書いてみたのは以下のコード： (defn insert [x sorted] (let [[heads tails] (split-with #(<= % x) sorted)] (concat heads [x] tails))) (defn insertion-sort [xs] (loop [[head & tail :as unsorte…

まあとりあえず。 (defn selection-sort [xs] (loop [unsorted xs, sorted []] (if (empty? unsorted) sorted (let [unsorted-indexed (map vector (range) unsorted) [min-i min-v] (apply min-key second unsorted-indexed) [heads [_ & tails]] (split-at…

書いてみる。 まずはletの中にベタ書き。 (defn quick-sort [col] (if (>= 1 (count col)) col (let [i (rand-int (count col)) pivot (nth col i) heads (take i col) tails (drop (inc i) col) col2 (concat heads tails) lesser (filter #(< % pivot) col…

前回 まあこれもありかも。 (def coins [500 100 50 10 5 1]) (defn f [[remainder & count-list] coin] (concat ((juxt rem quot) remainder coin) count-list)) (defn coin-count2 [n] (->> coins (reduce f (list n)) next reverse)) reduceの戻り値を、…

前回 ふと気づいたのだが、この問題ってreduceじゃなくてreductionsで書けば、「fの中でvectorを作成してそれを戻り値のvectorに入れて・・・」というvector入れ子状態を避けられる。 (def coins [500 100 50 10 5 1]) (defn f [[last-count remain] coin] (…

とりあえずiterate版も貼っておく。 (defn merge ([col] col) ([[head1 & rest1 :as col1] [head2 & rest2 :as col2]] (cond (some empty? [col1 col2]) (concat col1 col2) (< head1 head2) (lazy-seq (cons head1 (merge rest1 col2))) :else (lazy-seq (c…

なんとなくやってみた。 (defn merge ([col] col) ([[head1 & rest1 :as col1] [head2 & rest2 :as col2]] (cond (some empty? [col1 col2]) (concat col1 col2) (< head1 head2) (lazy-seq (cons head1 (merge rest1 col2))) :else (lazy-seq (cons head2 (…

Project Eulerをブログ用に解いていると、 答えを出す 2.高速化 3.コードの美化 の順番でかなり書き直しが必要なので、ただ単に解き散らかすのに比べてべらぼうに時間がかかる。 息抜きにIT速報を見ていたら、タイムリーなことに硬貨関連の問題が出ていた。 …

前回からの続き。

第三十一問 合計で200p（２００ペンス＝２ポンド）になるコインの組み合わせが何通りあるかを計算する。

第三十問 二桁以上の整数で、その数の各桁の５乗の和と等しいものを選んで足し合わせる。

第二十九問 a=2...100、b=2...100でabの取り得る個別の値の総数を求める。

第二十八問 数字の渦の角の和。

第二十七問 x=0..nで、 x2 + a*x + b がすべて素数となるnの値が最大となるaとbを求める。

素数算出アルゴリズムで最も有名なものは多分エラトステネスの篩だろう。発見した素数の倍数を消していく（篩にかけていく）ことによって、残った数の中で最小のものが素数だとわかる。そのプロセスを繰り返していくことで、一定のn以下のすべての素数が効率…

第二十六問 1/nを小数として表した時に、循環小数となるものの中で循環部分が一番長いnを求める。

第二十五問 桁数が１０００以上の最小のフィボナッチ数を求める。

第二十四問 ０〜９までの数字すべてを使った文字列の辞書式順序で、百万番目になるものは何か。

第二十三問 過剰数の和として表せないすべての数字の和を求める。

第二十二問 名前のリストが入ったテキストファイルがあって、その名前をソートし、位置のインデックスと文字のスコアをかけあわせた数字の和を求める。

第二十一問 １００００未満の友愛数の和を求める。