作者: Hiroshi Shinohara
日時: 2003/8/21(00:31)
Iconミニ講座４（フィルター）
　今回は、正整数の部分和への分解で、結構な数のパターンが生成されますので、
これに制限を掛けます。　分割数の制限と最小数の制限を付けられるようにします。
　前回の n_divd.icn に制限を付ける処理を追加しても良いのですが、降順のみの
制限を付けるだけで結構面倒で、これを修正する気が起きません。
　そこで、n_divd.icnはそのままにして、n_divdを呼ぶ方で制限を付けようと思い
ます。
　あるプログラムの処理結果を、別のプログラムが加工して、更に別のプログラムに
渡すことを、フィルターと言いますので、その類のプログラム構成のやり方となり
ます。　こんな格好の構成です。
 +----------------+      +--------------+      +--------------+
 | n_divd         |      | n_divdf      |      | main         |
 | 正整数分割生成 | ---> |  分割数制限  | ---> |  結果を使用  |
 |                |      |  最小数制限  |      |              |
 |                |      |   フィルター |      |              |
 |  generator     |      |   generator  |      |              |
 +----------------+      +--------------+      +--------------+

-----^ N_DIVDF.ICN ( date:03-08-20 time:23:48 ) ------------<cut here
####################
# 正整数分割　分割数・最小数制限付き
####################
# n_divdf.icn Rev.1.0 2003/08/20 windy 風つかい H.S.
####################
# Usage n_divdf 正整数 最大分割数 最小数
# 与えられた数字を部分和に分解する。結果は降順の分解のみ。
# 例:5->[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]
#    この中で、最大分割数、最小数の制限に合うものを出力する。
# This file is in the public domain.

procedure main(args)
  Usage := "n_divd 正整数 最大分割数 最小数"
  if *args   < 1 then stop(Usage) # コマンドライン引数が無ければ Usage表示
  if args[1] < 1 then stop(Usage) # 正数でなければ Usage表示
  n    := args[1]         # ↓defaultはなるべく生成パターンが少なくなるよう
  ndiv := \args[2] | 1    # defaultの最大分割数は、１（分割せず）
  nmin := \args[3] | *n   # defaultの最小数は、分割される数そのもの

  write(n," を、最大分割数 ",ndiv,"、最小数 ",nmin," にて分割")

  # ↓正整数分割 generatorから順次結果を取り出し
  every L := n_divdf(n,ndiv,nmin) do show_sl(L)
                                  #     ↑listの内容を表示する
end

####################
# 正整数分割 generator
####################
# 5=3+2 等に数字分割する。この procedureは n_divdを呼びフィルターを掛けている。
# 分割パターンが多すぎる時に、制限をかけるために使用。
# arg [1]: 分割する元の数
#     [2]: 最大分割数
#     [3]: 最小数
# value  : list
procedure n_divdf(r,ndiv,nmin)
  every L := n_divd(r) do {            # r の分割結果を取り出し
    if *L <= ndiv then {               # 分割数チェック（listのサイズチェック）
      if L[*L] >= nmin then suspend L  # 最小数チェック（降順に入っているので
    }                                  # 末尾の要素をチェック）
  }
end

####################
# 正整数分割 generator
####################
# 5=3+2 等に分割する。分割は降順のみ許す。（例 5=2+3は除外）
# arg [1]: 分割される元の数（再帰の場合は、前の処理の余り）
#     [2]: 最大数  （5=2+2+1 の場合に、最初の 2の時 3が余るが、再帰して 3の
#          分割を始める時、3からではなく 2から始めるための細工。降順手当。）
# value  : 分解結果の数。listに格納
# Usage  : every L := n_divd(r) do ...
procedure n_divd(r,max)
  /max := r                       # 指定無きは、分割される元の数そのもの
  if r < 1 then fail              # 念のため
  if r = 1 then return [1]        # 再帰終了

  # r >= 2 の場合
  if r > max then rs := max       # 分割（取り去る）数の最大数の設定。
             else rs := r         # 分割される数か 最大数指定の 小さい方
  every i :=  rs to 1 by -1 do {  # 上記指定数〜１迄、順に−１しながら
    rr := r -i                    # 新たな余り
    if rr = 0      then suspend [i]                   # 余りが無ければ
    # 余りがあれば、再帰処理
    else if rr > i then suspend [i] ||| n_divd(rr,i)  # 余りが大き過ぎる時
                   else suspend [i] ||| n_divd(rr)
  }
end

# 以下は、Icon入門講座より

####################
# listの 内容表示
####################
# arg   : list
# value : null
# Usage : show_sl(L)
# 最終的に stringか numberが要素であること
# Icon入門講座（１３）,Icon入門講座３（１５）

procedure show_sl(list)
# listの内容表示（test／表示用）
  every writes(" ",!list)
  write()
  return
end
-----$ N_DIVDF.ICN ( lines:86 words:320 ) ------------------<cut here

　n_divdf 9 3 3 >eee　とすると、結果はこうなります。　相当、制限が付けられ
ますね。
-----^ EEE ( date:03-08-21 time:00:00 ) --------------------<cut here
9 を、最大分割数 3、最小数 3 にて分割
 9
 6 3
 5 4
 3 3 3
-----$ EEE ( lines:5 words:13 ) ----------------------------<cut here

　さて、次回は、まとめです。

風つかい(hshinoh@...)
IconのWWWは、  http://www.cs.arizona.edu/icon/
UniconのWWWは、http://unicon.sourceforge.net/index.html
BGM: Battery's not included ／ 森山威男＆杉本喜代志