F# で基数変換をする

異なる n 個の記号を r 個並べたときの全ての組み合わせを知りたくなったので、基数変換のプログラムを書きました。

最近、特に数学に関する分野のことは、F# で書くことが多くなってきたと感じます。

Excel の BASE関数？　よくわかんないなぁ。

実行環境
どうして？
完成形
- 実行結果
N進法から10進法へ
新たに学んだこと
本当にしたかったこと
結び
参考

実行環境

Windows 10 21H2 (OS Build 19044.1526)
F# 6.0
F# インタラクティブ 12.0.0.0
.NET 6.0.101

どうして？

「どうして基数変換で全ての組み合わせを作れるの？」という意味の質問でしたら、「N進法」について知れば解決です。

たとえば普段私たちが使っている「10進法」というのは「0123456789」の10種類の記号を順番に組み合わせて数を表す方法です。「2進法」では「01」の2種類の記号を、「16進法」では「0123456789ABCDEF」の16種類の記号を順番に組み合わせて数を表します。このように、N種類の記号の組み合わせで数を表す方法を「N進法」と呼び、Nのことを「基数」(radix) と呼びます。10進法で表現している数を2進法で表現しなおしたり、2進法の数を16進法にしたりすることを「基数変換」(radix conversion) と呼びます。

もうおわかりでしょうか。「N種類の記号を順番に組み合わせる」というN進法と、「異なる n 個の記号を r 個並べたときの全ての組み合わせを作る」という処理は、非常によく似ているわけです。試しに「0~9」の10種類の記号を3個並べたときの全ての組み合わせを考えるなら、000, 001, 002, ... , 997, 998, 999 という風に、0から10³-1 = 999 まで10進法で数えるだけで済みます。5種類の記号を5つ並べる組み合わせなら、0から5⁵-1 = 3124 まで、00000, 00001, 00002, 00003, 00004, 00010, 00011, ... , 44442, 44443, 44444 と5進法で数えるだけです。N進法は数を表しているわけですから、当然組み合わせに重複がありません。これが、全ての組み合わせの列挙に基数変換を使う理由です。

「どうしてわざわざそんなことするの？」という意味の質問でしたら、楽しいからです。

完成形

数字、アルファベット大文字、アルファベット小文字、ひらがな、カタカナ、全て使うことで、229進法まで対応しています。

Excel の BASE関数？　36進法までしか対応してないからね。

// 1つの整数を10進法から229進法に変換する関数
// int -> string
let radixConversionOneChar number =
    match number with
    | var when var <= 9 -> string number // 0-9
    | var when var <= 35 -> number - 10 + (int 'A') |> char |> string // A-Z
    | var when var <= 61 -> number - 36 + (int 'a') |> char |> string // a-z
    | var when var <= 144 -> number - 62 + ('ぁ' |> char |> int) |> char |> string // ぁ-ん
    | var when var <= 228 -> number - 145 + ('ァ' |> char |> int) |> char |> string // ァ-ヴ
    | _ -> "";;

// 指定した桁数でゼロ埋めする関数
// int -> string -> string
let padWithZero digit (text : string) =
    if digit <= text.Length then
        text
    else
        digit - text.Length // ゼロ埋めのゼロの個数を求める
        |> string
        |> (fun x -> (0).ToString("D" + x))
        |> (fun x -> x + text);; // 先頭にゼロをつける

// これを呼び出す
// int -> int -> int -> string
let radixConversion radix digit number =
    
    // 割り算を繰り返す再帰関数
    // int -> int -> string -> string
    let rec radixConversionRec number radix acc = 
        
        // 「整数 / 基数」の商
        let quotient = number / radix
        
        // 商を基数変換したもの
        let quotientOneChar = radixConversionOneChar quotient
        
        // 余りを基数変換したもの
        let remainderOneChar = number % radix |> radixConversionOneChar
        
        match quotient with
        | var when var < radix -> quotientOneChar + remainderOneChar + acc
        | _ -> radixConversionRec quotient radix (remainderOneChar + acc)
    
    // 基数変換したあとゼロ埋めする
    radixConversionRec number radix ""
    |> padWithZero digit;;

実行結果

radixConversion 62 10 106312;;
// 0000000Rei

radixConversion 229 3 8023389;;
// エヴァ

N進法から10進法へ

10進法からN進法に変換する関数は作りましたが、10進法に戻す関数は忘れていました。呪いはかけるだけで解けない荒地の魔女みたいになってしまった。まぁそのうち作るわよ。

新たに学んだこと

ゼロ埋めの関数内で、先頭につけるゼロの羅列を作るために int の ToString() メソッドを使おうとしたのですが、0.ToString("D" + x) としたらエラーが出ました（x には必要なゼロの桁数が渡っていて、D5 のような書式指定子を作っています）。苦し紛れに (0).ToString("D" + x) とすることで難を逃れましたが、String.replicate 関数を使ってもよかったなと思いました。