お気楽 Standard ML of New Jersey 入門

はじめに

今回は簡単な例題として、「順列 (permutation)」と「組み合わせ (combination)」を取り上げます。

●順列の生成

異なる n 個の順列の総数は、n の階乗 (n!) だけあります。たとえば、3 つの整数 1, 2, 3 の順列は次に示すように 6 通りあります。

1 2 3,  1 3 2,  2 1 3,  2 3 1,  3 1 2,  3 2 1

順列を生成するプログラムは再帰定義で簡単に作ることができます。[1, 2, 3] の順列を生成する場合、最初に 1 で始まる順列を生成します。これは 1 を取り除いた数字 [2, 3] の順列を生成することで実現できます。

次は 2 で始まる順列を生成します。同様に、2 を取り除いた数字 [1, 3] の順列を生成すればいいわけです。[2, 3] や [1, 3] の順列を生成する場合も同じように考えることができます。

プログラムは次のようになります。

リスト : 順列の生成 (1)

(* int list の表示 *)
fun print_intlist xs =
  (app (fn x => (print (Int.toString x); print " ")) xs;
   print "\n")

(* 要素の削除 *)
fun remove(_, nil) = nil
|   remove(x, y::ys) =
  if x = y then remove(x, ys) else y :: remove(x, ys)

(* 順列の生成 *)
fun permutation f n xs =
  let
    fun perm(0, _, a) = f (rev a)
    |   perm(n, xs, a) =
      app (fn x => perm(n - 1, remove(x, xs), x::a)) xs
  in
    perm(n, xs, nil)
  end

関数 permutation f n xs は高階関数で、引数 n が選ぶ要素の個数、引数 xs がリスト、引数 f が生成した順列に適用する関数です。

たとえば、順列が数字のリストであれば、int list を表示する関数 print_intlist を渡すことで、生成した順列を表示することができます。実際の処理は局所関数 perm で行います。

perm の引数 n が選ぶ要素の個数、引数 xs がリストです。引数 a は累積変数で、選んだ数字を格納するリストです。n が 0 の場合、順列がひとつ完成しました。関数 rev で a を逆順にしてから関数 f に渡します。選んだ数字は a の先頭に追加していくので、逆順になることに注意してください。

n が 0 でなければ、数字を一つ選んで perm を再帰呼び出しします。数字の選択はリストの先頭から順番に行えばいいので、高階関数 app を使っています。

匿名関数でリストの要素 x を受け取り、この中で prem を再帰呼び出しします。n を -1 して、xs から x を削除します。そして、x を a に追加します。これで x を選択したことになります。

関数 remove x ys はリスト ys から x と等しい要素を削除します。高階関数 List.filter を使う場合は次のようになります。

fun remove(x, ys) = List.filter (fn y => x <> y) ys

それでは、実際に試してみましょう。

- permutation;
val it = fn : (''a list -> unit) -> int -> ''a list -> unit

- permutation print_intlist 3 [1,2,3];
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
val it = () : unit

正常に動作していますね。

●順列をリストに格納する

生成した順列をリストに格納して返す場合は、List.foldr を使うと簡単です。プログラムは次のようになります。

リスト : 順列の生成 (2)

fun permutation_list n xs =
  let
    fun perm(0, _, a, b) = rev a :: b
    |   perm(n, xs, a, b) =
      List.foldr (fn(x, c) => perm(n - 1, remove(x, xs), x::a, c)) b xs
  in
    perm(n, xs, nil, nil)
  end

局所関数 perm は permutation の局所関数を改造したもので、生成した順列を第 4 引数 b のリストに格納します。perm は順列を格納したリスト (第 4 引数) をそのまま返します。perm を呼び出す場合、この返り値を第 4 引数に渡すことで、生成した順列を格納していくことができます。

List.foldr の初期値 (第 3 引数) に引数 b を渡すことで、匿名関数の第 2 引数 c に順列を格納するリストを渡します。あとは perm を再帰呼び出しすると、その返り値は次に匿名関数を呼び出すときの引数 c に渡されるので、順列を格納したリストを perm に渡していくことができます。

それでは実行結果を示します。

- permutation_list;;
val it = fn : int -> ''a list -> ''a list list

- permutation_list 3 [1,2,3];
val it = [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] : int list list

正常に動作していますね。ところで、permutation と permutation_list は remove を使って要素を削除しているので、関数の型は等値型に制限されます。リストの中から要素を一つ選択する関数 select を定義すると、この制約を外すことができます。興味のある方は「問題」に挑戦してみてください。

●組み合わせの数

次は組み合わせの数を求めるプログラムを作ってみましょう。ここでは組み合わせの数を \({}_n \mathrm{C}_r\) と表記します。\({}_n \mathrm{C}_r\) を求めるには、次の公式を使えば簡単です。

皆さんお馴染みの公式ですね。ところが、整数値の範囲が限られているプログラミング言語では、この公式を使うと乗算で「桁あふれ」を起こす恐れがあります。SML/NJ は Common Lisp のような多倍長整数をサポートしていないので、この公式をそのままプログラムするわけにはいきません。そこで、次の公式を使うことにします。

この式は \({}_n \mathrm{C}_r\) と \({}_n \mathrm{C}_{r-1}\) の関係を表しています。あとは階乗と同じように、再帰定義を使って簡単にプログラムできます。次のリストを見てください。

リスト : 組み合わせの数を求める

fun comb(n, r) =
  if n = r orelse r = 0 then 1
  else comb(n, r - 1) * (n - r + 1) div r  

とても簡単ですね。ところで、SML/NJ の整数 (int) は 32 bit 処理系で ~1073741824 から 1073741823 までなので、このプログラムでも桁あふれする場合があります。どこまで計算できるか試してみましょう。

- comb(16, 8);
val it = 12870 : int
- comb(18, 9);
val it = 48620 : int
- comb(20, 10);
val it = 184756 : int
- comb(22, 11);
val it = 705432 : int

- comb(24, 12);
val it = 2704156 : int
- comb(26, 13);
val it = 10400600 : int
- comb(28, 14);
val it = 40116600 : int
- comb(30, 15);
uncaught exception overflow

SML/NJ の場合、桁あふれが発生すると例外 overflow が送出されます。桁あふれを起こさないようにするには、モジュール IntInf を使います。SML/NJ はコロン ( : ) を使ってデータ型を指定することができます。

リスト : 組み合わせの数を求める (2)

fun comb1(n, r) =
  if n = r orelse r = 0 then 1 : IntInf.int
  else comb1(n, r - 1) * (n - r + 1) div r  

(* 関数の引数で型指定してもよい *)
fun comb1(n : IntInf.int, r) =
  if n = r orelse r = 0 then 1
  else comb1(n, r - 1) * (n - r + 1) div r  

val comb1 = fn : ?.intinf * ?.intinf -> ?.intinf

返り値の整数 1 に : IntInf.int を指定することで、計算を多倍長整数で行うことができます。また、関数の引数で型指定を行ってもかまいません。それでは実行してみましょう。

- comb1(30,15);
val it = 155117520 : ?.intinf
- comb1(50,25);
val it = 126410606437752 : ?.intinf
- comb1(100,50);
val it = 100891344545564193334812497256 : ?.intinf

このように、IntInf モジュールを使って多倍長整数で計算を行うことができます。

●パスカルの三角形

それでは、関数 comb を使って「パスカルの三角形」を作ってみましょう。次の図を見てください。

                 １                                 0Ｃ0
               ／  ＼                              ／  ＼
             １      １                         1Ｃ0    1Ｃ1
           ／  ＼  ／  ＼                      ／  ＼  ／  ＼
         １      ２      １                 2Ｃ0    2Ｃ1    2Ｃ2
       ／  ＼  ／  ＼  ／  ＼              ／  ＼  ／  ＼  ／  ＼
     １      ３      ３      １         3Ｃ0    3Ｃ1    3Ｃ2    3Ｃ3
   ／  ＼  ／  ＼  ／  ＼  ／  ＼      ／  ＼  ／  ＼  ／  ＼  ／  ＼
 １      ４      ６      ４      １ 4Ｃ0    4Ｃ1    4Ｃ2    4Ｃ3    4Ｃ4 

                        図 : パスカルの三角形

パスカルの三角形は、左側の図のように両側がすべて 1 で、内側の数はその左上と右上の和になっています。これは \((a + b)^n\) を展開したときの各項の係数を表しています。そして、その値は右側の図のように組み合わせの数 \({}_n \mathrm{C}_r\)に対応しています。

きれいな三角形にはなりませんが、パスカルの三角形を表示するプログラムを示します。

リスト : パスカルの三角形

fun print_int n = print(Int.toString(n) ^ " ")

fun pascal x =
  let
    fun pas(n, r) =
      if x < n then ()
      else if n < r then (print "\n"; pas(n + 1, 0))  
      else (print_int(comb(n, r)); pas(n, r + 1))
  in
    pas(0, 0)
  end

手続き型言語では「二重ループ」で簡単にプログラムできるのですが、SML/NJ の while ループはまだ説明していないので、再帰定義でプログラムしました。pas(n, r) で x < n の場合が再帰呼び出しの停止条件です。

- pascal 10;
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
val it = () : unit

1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 5
2 3 4, 2 3 5, 2 4 5, 3 4 5

リスト : 組み合わせの生成

fun combination f r xs = 
  let
    fun comb(0, _, a) = f (rev a)
    |   comb(_, nil, _) = ()
    |   comb(r, y::ys, a) = (comb(r - 1, ys, y::a); comb(r, ys, a))
  in
    comb(r, xs, nil)
  end

- combination print_intlist 3 [1,2,3,4,5];
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
val it = () : unit

リスト : 組み合わせの生成 (2)

fun combination_list r xs = 
  let
    fun comb(0, _, a, b) = rev a :: b
    |   comb(_, nil, _, b) = b
    |   comb(r, y::ys, a, b) = comb(r - 1, ys, y::a, comb(r, ys, a, b))
  in
    comb(r, xs, nil, nil)
  end

val combination_list = fn : int -> 'a list -> 'a list list

- combination_list 3 [1,2,3,4,5];
val it =
  [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],
   [3,4,5]] : int list list

リスト : 解答例

fun flatten nil = nil
|   flatten (x::xs) = x @ flatten xs

fun flatmap f nil = nil
|   flatmap f (x::xs) = f x @ flatmap f xs

(* 別解 
fun flatmap f xs = flatten (map f xs)
*)

fun select nil = nil
|   select [x] = [(x, nil)]
|   select (x::xs) = (x, xs) :: map (fn(y, ys) => (y, x::ys)) (select xs)

fun permutation_list1 n xs =
  if n = 0 then [nil]
  else flatmap (fn(y, ys) => map (fn zs => y::zs) (permutation_list1 (n - 1) ys)) (select xs)

fun iota(n, m) =
  if n > m then []
  else n :: iota(n + 1, m)

fun derangement f m =
  let
    fun perm(_, nil, a) = f (rev a)
    |   perm(n, xs, a) =
      app (fn x => if x = n then () else perm(n + 1, remove(x, xs), x::a)) xs
  in
    perm(0, iota(0, m - 1), nil)
  end

- flatten;
val it = fn : 'a list list -> 'a list
- flatten [[1,2,3],[4,5,6],[7,8,9]];
val it = [1,2,3,4,5,6,7,8,9] : int list

- flatmap;
val it = fn : ('a -> 'b list) -> 'a list -> 'b list
- map (fn x => [x,x,x]) [1,2,3,4,5];
val it = [[1,1,1],[2,2,2],[3,3,3],[4,4,4],[5,5,5]] : int list list
- flatmap (fn x => [x,x,x]) [1,2,3,4,5];
val it = [1,1,1,2,2,2,3,3,3,4,4,4,5,5,5] : int list

- select;
val it = fn : 'a list -> ('a * 'a list) list
- select [1,2,3,4];
val it = [(1,[2,3,4]),(2,[1,3,4]),(3,[1,2,4]),(4,[1,2,3])]
  : (int * int list) list

- permutation_list1;
val it = fn : int -> 'a list -> 'a list list
- permutation_list1 3 [1,2,3];
val it = [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] : int list list
- permutation_list1 4 [1,2,3,4];
val it =
  [[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,2,3],[1,4,3,2],[2,1,3,4],
   [2,1,4,3],[2,3,1,4],[2,3,4,1],[2,4,1,3],[2,4,3,1],[3,1,2,4],[3,1,4,2],
   [3,2,1,4],[3,2,4,1],...] : int list list

- derangement;
val it = fn : (int list -> unit) -> int -> unit
- derangement print_intlist 3;
1 2 0
2 0 1
val it = () : unit
- derangement print_intlist 4
= ;
1 0 3 2
1 2 3 0
1 3 0 2
2 0 3 1
2 3 0 1
2 3 1 0
3 0 1 2
3 2 0 1
3 2 1 0
val it = () : unit