2013-04-06

F#の無限シーケンスで素数列

Haskellでよくある

primes = [2, 3]
       ++ filter (\n -> all (\p -> mod n p /= 0)
                 $ takeWhile (\p -> p*p <= n) primes) [5, 7 ..]

的なやつを。

let infty n m = Seq.initInfinite (fun i -> n + i * m)

let rec primes = seq {
    yield! [2; 3]
    for i in infty 5 2 do
        if Seq.forall (fun x -> i % x <> 0)
                  (Seq.takeWhile (fun x -> x*x <= i) primes)
        then yield i
    }

なんか若干「そういう言語じゃねーから」みたいな感じがしますね。
F#は正格評価の言語なので、C#でいうとIEnumerable<T>とか書く時のごてっとした感じ？

2013-02-24

make10

プログラミング Haskell

「8 8 9 9」のmake10を四則演算でやれと言う話なので。分かんないので。
アルゴリズムとしては「切符の番号で10を作る」のと同じです。カッコよく言うと分割統治法。コードはあんま美しくないけど。

import Data.List


data Expr = C Int | Add Expr Expr | Sub Expr Expr | Mul Expr Expr | Div Expr Expr

instance Show Expr where
    show (C x)     = show x
    show (Add x y) = "(" ++ (show x) ++ "+" ++ (show y) ++ ")"
    show (Sub x y) = "(" ++ (show x) ++ "-" ++ (show y) ++ ")"
    show (Mul x y) = "(" ++ (show x) ++ "*" ++ (show y) ++ ")"
    show (Div x y) = "(" ++ (show x) ++ "/" ++ (show y) ++ ")"

instance Eq Expr where
    (C x)     == (C y)     = x == y
    (Add x y) == (Add u v) = (x == u && y == v) || (x == v && y == u)
    (Sub x y) == (Sub u v) = (x == u && y == v)
    (Mul x y) == (Mul u v) = (x == u && y == v) || (x == v && y == u)
    (Div x y) == (Div u v) = (x == u && y == v)
    _         == _         = False


search n a = nub $ concat $ map (\(e,b) -> _search n b (C e)) (picks a)

_search :: Int -> [Int] -> Expr -> [Expr]
_search n a p = if null a
                    then (if eval p == Just (fromIntegral n) then [p] else [])
                    else concat $ map (\(e,b) -> concat $ map (\q -> _search n b q) (opr (C e) p)) (picks a)
 where
     opr x y = [Add x y, Sub x y, Sub y x, Mul x y, Div x y, Div y x]

picks a = [pickAt i a | i <- [0..(length a)-1]]
pickAt n l = (\(a,b) -> (head b, a ++ tail b)) (splitAt n l)

eval :: Expr -> Maybe Rational
eval (C x) = Just (fromIntegral x)
eval (Add x y) = eval x >>= (\m -> eval y >>= Just.(+ m))
eval (Sub x y) = eval x >>= (\m -> eval y >>= Just.(\n -> subtract n m))
eval (Mul x y) = eval x >>= (\m -> eval y >>= Just.(* m))
eval (Div x y) = eval x >>= (\m -> eval y >>= (\n -> if n == 0 then Nothing else Just (m / n)))

出力結果は

*Main> search 10 [2,3,7,7]
[(7+((7+2)/3)),((3+(7*2))-7),(3-(7-(7*2))),(3+((7*2)-7)),(3+((7+7)/2))]
*Main> search 10 [8,8,9,9]
[]

みたいな。要するに最初のは解無しっぽいという話でした。

2013-02-22

連分数

数学

$1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{\ddots}}}$
みたいなのを連分数と呼ぶ。これだとスペースを取るので
$1 + \frac{1}{1} {\ \atop+} \frac{1}{1} {\ \atop{+ \cdots}}$
とか(低い位置の+は直前の分数の分母にそれ以降を足す感じ)、分子が皆1の時は+の左の数字を並べて $[1; 1, 1, \ldots]$ とも書く。
値を求めるには、これを $x$ と置くと
$x = 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{\ddots}}} = 1 + \frac{1}{x}$
より $x^2 - x - 1 = 0$ となるから
$x = \frac{1 \pm \sqrt{5}}{2}$
$x$ は普通に考えて正なので、 $\pm$ の正を取るとこの値は黄金比 $\phi$ である。従って
$\phi = 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{\ddots}}}$
が成り立つ。

実数の連分数展開

ある実数を整数部と小数部に分けられれば、それを連分数に展開できる。
例えば円周率 $\pi = 3.1415926535\ldots$ は
$\pi = 3 + \frac{1}{\frac{1}{0.14159\ldots}} = 3 + \frac{1}{7.0625\ldots} = 3 + \frac{1}{7 + \frac{1}{\frac{1}{0.0625\ldots}}} = 3 + \frac{1}{7 + \frac{1}{15.997\ldots}}$
という感じで $\pi = [3; 7, 15, 1, 292, 1, \ldots]$ になる(WolframAlphaで計算)。
ここで $1/15.997\ldots \approx 0$ と近似すると、
$\pi \approx 3 + \frac{1}{7} = \frac{22}{7}$
という有名な近似分数が現れる。

円周率は二進法なら11.0010010...だし十六進法なら3.243f6a88...だが、連分数展開により現れる数列は円周率の値のみで定まる。
それ故、連分数展開はより数の自然な表現を与えるとも言えよう。

一次分数変換

ところで、定数 $a,b,c,d \ (ad-bc \ne 0)$ について
$f(x) = \frac{ ax+b }{ cx+d }$
なる函数を一次分数変換とかメビウス(Möbius)変換とか呼ぶ。 $ad-bc=0$ では $f(x) = 1$ に「潰れる」ので除いておく。
一次分数変換 $f(x) = \frac{ ax+b }{ cx+d }$ 及び $g(x) = \frac{ a'x+b' }{ c'x+d' }$ を合成してみると
$f \circ g(x) = \frac{ a \frac{ a'x+b' }{ c'x+d' } + b }{ c \frac{ a'x+b' }{ c'x+d' } + d } = \frac{ (aa'+bc')x + (ab'+bd') }{ (ca'+dc')x + (cb'+dd') }$
となる訳だが、これは
$\begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} a' & b' \\ c' & d' \end{pmatrix} = \begin{pmatrix} aa'+bc' & ab'+bd' \\ ca'+dc' & cb'+dd' \end{pmatrix}$
という行列積の要素と見事に符合している！　ので、
$f(x) = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \cdot x$
という表記を用いると一次分数変換の合成等を行列の計算で扱える。

連分数と行列

さて
$\frac{b_1}{a_1 + \frac{b_2}{ a_2 +_{ \ddots \frac{b_N}{a_N} }}}$
を眺めると、これが一次分数変換
$f_n(x) = \begin{pmatrix} 0 & b_n \\ 1 & a_n \end{pmatrix} \cdot x = \frac{b_n}{x + a_n}$
により
$f_1 \circ f_2 \circ f_3 \circ \cdots f_N(0) = \begin{pmatrix} 0 & b_1 \\ 1 & a_1 \end{pmatrix} \begin{pmatrix} 0 & b_2 \\ 1 & a_2 \end{pmatrix} \cdots \begin{pmatrix} 0 & b_N \\ 1 & a_N \end{pmatrix} \cdot 0$
と表せる事に気付く。
すると、例えば $[1;1,1,1,\ldots]$ の場合、 $(\phi, \psi) = \left( \frac{1+\sqrt{5}}{2} , \frac{1-\sqrt{5}}{2} \right)$ と置いて
$-\frac{1}{\sqrt{5}} \begin{pmatrix} \psi & -1 \\ -\phi & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ \phi & \psi \end{pmatrix} = \begin{pmatrix} \phi & 0 \\ 0 & \psi \end{pmatrix}$ （'13/03/06 係数の誤りを訂正）
と対角化する事で
${\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}}^n = -\frac{1}{\sqrt{5}} \begin{pmatrix} 1 & 1 \\ \phi & \psi \end{pmatrix} \begin{pmatrix} \phi^n & 0 \\ 0 & \psi^n \end{pmatrix} \begin{pmatrix} \psi & -1 \\ -\phi & 1 \end{pmatrix} = -\frac{1}{\sqrt{5}} \begin{pmatrix} \psi \phi^n - \phi \psi^n & -\phi^n + \psi^n \\ \psi \phi^{n+1} - \phi \psi^{n+1} & -\phi^{n+1} + \psi^{n+1} \end{pmatrix}$
より
${\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}}^n \cdot 0 = \frac{ -\phi^n + \psi^n }{ -\phi^{n+1} + \psi^{n+1} }$
を得る。 $|\psi / \phi| < 1$ より
$\lim_{n \to +\infty} {\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}}^n \cdot 0 = \frac{1}{\phi}$
なので、再び
$[1; 1, 1, \ldots] = 1 + \frac{1}{\phi} = \phi$
を得る。

級数の連分数展開

級数を無理やり連分数に展開して
$\sum_{n=0}^{+\infty} a_n = a_0 \left( 1 + \sum_{n=1}^{+\infty} \frac{a_n}{a_0} \right) = \frac{a_0}{ 0 + \frac{1}{1 + \sum_{n=1}^{+\infty} \frac{a_n}{a_0}} } = \frac{a_0}{0} {\ \atop+} \frac{1}{1} {\ \atop+} \sum_{n=1}^{+\infty} \frac{a_n}{a_0}$
と出来るから、
$\sum_{n=0}^{+\infty} a_n = \frac{a_0}{0} {\ \atop+} \frac{1}{1} {\ \atop+} \frac{a_1/a_0}{0} {\ \atop+} \frac{1}{1} {\ \atop+} \frac{a_2/a_1}{0} {\ \atop+} \frac{1}{1} {\ \atop{+\cdots}}$
又は「約分」して
$\sum_{n=0}^{+\infty} a_n = \frac{a_0}{0} {\ \atop+} \frac{a_0}{a_0} {\ \atop+} \frac{a_1}{0} {\ \atop+} \frac{a_1}{a_1} {\ \atop+} \frac{a_2}{0} {\ \atop+} \frac{a_2}{a_2} {\ \atop{+\cdots}}$
となる。
ここで
$\frac{a}{b} {\ \atop+} \frac{c}{0} {\ \atop+} F = \frac{a}{b} {\ \atop+} \frac{c}{F} = \frac{aF}{bF} {\ \atop+} \frac{cF}{F} = \frac{aF}{bF+c} = \frac{aF+\frac{a}{b}c-\frac{a}{b}c}{bF+c} = \frac{a}{b} - \frac{\frac{a}{b} c}{c} {\ \atop+} bF$
より分母位置の0を消去できる。即ち
$\sum_{n=0}^{+\infty} a_n = \frac{a_0}{0} {\ \atop+} \frac{1}{1} {\ \atop+} \frac{a_1/a_0}{0} {\ \atop+} \frac{1}{1} {\ \atop+} \frac{a_2/a_1}{0} {\ \atop+} \frac{1}{1} {\ \atop{+\cdots}}$
$= \frac{a_0}{0} {\ \atop+} \left( 1 - \frac{a_1/a_0}{a_1/a_0} {\ \atop+} \frac{1}{1} {\ \atop+} \frac{a_2/a_1}{0} {\ \atop+} \frac{1}{1} {\ \atop{+\cdots}} \right)$
$= \frac{a_0}{1} {\ \atop-} \frac{a_1/a_0}{a_1/a_0} {\ \atop+} \frac{1}{1} {\ \atop+} \frac{a_2/a_1}{0} {\ \atop+} \frac{1}{1} {\ \atop+} \frac{a_3/a_2}{0} {\ \atop+} \frac{1}{1} {\ \atop{+\cdots}}$
$= \frac{a_0}{1} {\ \atop-} \frac{a_1/a_0}{a_1/a_0 + 1} {\ \atop-} \frac{a_2/a_1}{a_2/a_1} {\ \atop+} \frac{1}{1} {\ \atop+} \frac{a_3/a_2}{0} {\ \atop+} \frac{1}{1} {\ \atop{+\cdots}}$
$= \frac{a_0}{1} {\ \atop-} \frac{a_1/a_0}{a_1/a_0 + 1} {\ \atop-} \frac{a_2/a_1}{a_2/a_1 + 1} {\ \atop-} \frac{a_3/a_2}{a_3/a_2 + 1} {\ \atop{-\cdots}}$
例えば $a_n = x^n / n!$ とすると、
$e^x = \frac{1}{1} {\ \atop-} \frac{x}{x + 1} {\ \atop-} \frac{x/2}{x/2 + 1} {\ \atop-} \frac{x/3}{x/3 + 1} {\ \atop{-\cdots}} = \frac{1}{1} {\ \atop-} \frac{x}{x + 1} {\ \atop-} \frac{x}{x + 2} {\ \atop-} \frac{2x}{x + 3} {\ \atop{-\cdots}}$
という指数函数の連分数展開が得られる。

こうした展開例については数学研究ノートの連分数の項に詳しい。（'17/08/04 移転していたのでリンク修正）

2013-02-22

和の比と比の和の不等式

数学

$\sum_{i=1}^{n} \frac{x_i}{a_i} > \frac{ \sum_{i=1}^{n} x_i }{ \sum_{i=1}^{n} a_i } \quad (n \ge 2,\, a_i, x_i > 0)$
を数学的帰納法により示す。

$n=2$ の時
$\frac{x_1}{a_1} + \frac{x_2}{a_2} - \frac{ x_1 + x_2 }{ a_1 + a_2 }$
$\frac{a_2 x_1 + a_1 x_2}{a_1 a_2} - \frac{ x_1 + x_2 }{ a_1 + a_2 }$
$= \frac{ (a_1 + a_2)(a_2 x_1 + a_1 x_2) - a_1 a_2 (x_1 + x_2) }{ a_1 a_2 (a_1 + a_2) }$
$= \frac{ a_2^2 x_1 + a_1^2 x_2 }{ a_1 a_2 (a_1 + a_2) }$
$> 0$
よって成り立つ。

$n = k$ の時に成り立つとすると
$\sum_{i=1}^{k} \frac{x_i}{a_i} > \frac{ \sum_{i=1}^{k} x_i }{ \sum_{i=1}^{k} a_i }$
ここで $(x_k, a_k) \to (x_k + x_{k+1}, a_k + a_{k+1})$ と置き換えると
$\sum_{i=1}^{k-1} \frac{x_i}{a_i} + \frac{ x_k + x_{k+1} }{ a_k + a_{k+1} } > \frac{ \sum_{i=1}^{k+1} x_i }{ \sum_{i=1}^{k+1} a_i }$
$n = 2$ の場合より
$\frac{x_k}{a_k} + \frac{ x_{k+1} }{ a_{k+1} } > \frac{ x_k + x_{k+1} }{ a_k + a_{k+1} }$
であるから
$\sum_{i=1}^{k+1} \frac{x_i}{a_i} > \sum_{i=1}^{k-1} \frac{x_i}{a_i} + \frac{ x_k + x_{k+1} }{ a_k + a_{k+1} } > \frac{ \sum_{i=1}^{k+1} x_i }{ \sum_{i=1}^{k+1} a_i }$
となり $n = k + 1$ でも成り立つ。

以上より任意の $n \ge 2$ について示された。 $\qed$

はてな記法の $\TeX$ を試してみようと、何かの証明に使おうとした補題を載せてみる。
はてなで使われてるmimeTeXは美しくないので、「LaTeXのオンライン数式画像生成ツールの比較」を参考に要所々々でCodecogsのを使ってみると好い感じかな？　ってゆう。

2012-11-17

形態素解析器

プログラミング自然言語解析 C#

C#から直截形態素解析器のライブラリを使いたいよぉ…ふぇぇ…って人に。
茶筌はツン過ぎて辛かっただって何ですかstring[]渡すだけなのに。

using System.Runtime.InteropServices;

class MeCab : IDisposable
{
    IntPtr ptr;

    [DllImport("libmecab.dll", CallingConvention = CallingConvention.Cdecl)]
    private extern static IntPtr mecab_new2(string arg);
    [DllImport("libmecab.dll", CallingConvention = CallingConvention.Cdecl)]
    private extern static IntPtr mecab_sparse_tostr(IntPtr m, string str);
    [DllImport("libmecab.dll", CallingConvention = CallingConvention.Cdecl)]
    private extern static void mecab_destroy(IntPtr m);

    public MeCab()
    {
        ptr = mecab_new2(@"-F%m\s%f[6]\s%f[0]\n");
    }
    public string sparse_tostr(string str_in)
    {
        return Marshal.PtrToStringAnsi(mecab_sparse_tostr(ptr, str_in));
    }
    public void Dispose()
    {
        mecab_destroy(ptr);
    }
}

class Chasen
{
    [DllImport("libchasen.dll", CallingConvention = CallingConvention.Cdecl)]
    extern static int chasen_getopt_argv([MarshalAs(UnmanagedType.LPArray, ArraySubType = UnmanagedType.LPStr, SizeParamIndex = 1)]string[] argv, IntPtr file);
    [DllImport("libchasen.dll", CallingConvention = CallingConvention.Cdecl)]
    extern static IntPtr chasen_sparse_tostr(string str_in);

    public Chasen()
    {
        string[] argv = { "", "-s", "-F", @"%m %M %H\n", null };

        if (chasen_getopt_argv(argv, IntPtr.Zero) == 1)
            throw new ArgumentException();
    }
    public string sparse_tostr(string str_in)
    {
        return Marshal.PtrToStringAnsi(chasen_sparse_tostr(str_in));
    }
}

跳慮跋考

興味も思考も行先不明