Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 今回はメルセンヌ数（Mersenne Number）が素数であるかどうかを判定するリュカ・テスト (Lucas–Lehmer primality test) を見ていきます。メルセンヌ数とは を素数とし…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 前回、素数列を生成するアルゴリズムを見ましたが、今回は素因数分解 (factorization into primes) をするアルゴリズムを見ていきます。参考 『Javaによるアルゴリズ…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 ちょっと別用で素数 (prime number) を生成するコードを書いたので、こちらのブログで整理しておきます。 別用記事で見たように Int や Long に対してなら2行で書けま…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 今回は最大公約数（GCD, Greatest Common Divsor）を求めるアルゴリズムを見ていきます。 最大公約数はアルゴリズムと言えばのユークリッド互除法で求められます。こ…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ。 今回は組合せの個数を計算するアルゴリズム。 その1では、あまり実用的ではないです…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 今回は再帰関数の例としてよく出てくる自然数の階乗と、それに関連する順列の個数を計算するアルゴリズムを見ていきます。 再帰関数の例としてよく出てくると言っても…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 今回は前回に引き続き、全順列を生成するアルゴリズムを見ていきます。 全開は『Java によるアルゴリズム事典』に載っている4つのアルゴリズムのうち1つ目のものを見…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 今回はある定まった次数（並べるモノの個数。 コード中では degree とする）の全順列を生成するアルゴリズムを見ていきます。 『Java によるアルゴリズム事典』には4…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 今回は順列に辞書順序で番号を付けたとき、与えられた順列とその番号との相互の変換を考えます。 ただし番号は Int などの通常の整数値ではなく、階乗進法で表された…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 今回は、階乗進法 (factorial representation) という数の表し方を見ていきます。階乗進法10進法が10を基数にしている、つまり10の累乗の級数で表されるのに対して、…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 以前に置換のアルゴリズムを扱ったときに、『Java によるアルゴリズム事典』に「置換の生成」がなくておかしいなぁと思ってたら、「順列」「順列の生成」の項目にある…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 『Java によるアルゴリズム事典』で、関数型プログラミングで書きやすそうなアルゴリズムがあったので Scala で書いてみた。 今回は、データに誤りが無いかチェックす…

『Java によるアルゴリズム事典』には載ってなかったんですが、n 個のモノの全置換を生成するコードを見ていきます（目次）。Scala では List などの順序付きのコレクション（正確には scala.collection.SeqLike トレイトのサブ型）では permutations() メソ…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 今回は指定された置換の符号を計算するアルゴリズム。 ここでは Java や Scala のコードで扱い易くするため、n 個の置換は1から n の整数ではなく、0から n-1 の整数…

『Java によるアルゴリズム事典』に載ってるコードを Scala かつ再帰（できる限り末尾再帰）で書いていこうシリーズ。 と言っても、他のことで使うコードでこの本に載ってるアルゴリズムを使うときに記事更新するので、たまにしか記事書かないと思います。数…